Cómo encontrar el carácter que ocurre con más frecuencia en una cadena

Las cadenas son un tema muy importante en la programación de entrevistas. Es aconsejable practicar algunos problemas de programación centrados en las cadenas antes de las entrevistas. En este artículo, aprenderá a encontrar el carácter que aparece con más frecuencia en una cadena.

Ejemplos para comprender el problema

Ejemplo 1: Sea la cadena dada "Makeuseof". El carácter 'e' aparece 2 veces en la cadena dada y todos los demás caracteres aparecen solo una vez. Por lo tanto, el carácter 'e' tiene la frecuencia más alta en la cadena dada.

Ejemplo 2: Deje que la cadena dada sea "Ella ve queso". El carácter 'e' aparece 6 veces en la cadena dada y todos los demás caracteres aparecen menos de 6 veces. Por lo tanto, el carácter 'e' tiene la frecuencia más alta en la cadena dada.

Enfoque para encontrar el carácter que ocurre con más frecuencia en una cadena

La técnica de hash es la forma más eficaz de encontrar el carácter que tiene la frecuencia más alta en una cadena. En esta técnica, la cadena se atraviesa y cada carácter de la cadena se convierte en una matriz de caracteres ASCII.

Deje que la cadena de entrada sea "Makeuseof", cada carácter de esta cadena se hash de la siguiente manera:

frecuencia ['M'] = 1

frecuencia ['a] = 1

frecuencia ['k'] = 1

frecuencia ['e'] = 2

frecuencia ['u'] = 1

frecuencia ['s'] = 1

frecuencia ['o'] = 1

frecuencia ['f'] = 1

Se devuelve el índice del valor máximo en la matriz de frecuencias. Aquí 2 es el valor más alto, por lo tanto, se devuelve 'e'.

Programa C ++ para encontrar el carácter con la frecuencia más alta

A continuación se muestra el programa C ++ para encontrar el carácter con la frecuencia más alta en una cadena:

Relacionados: Cómo contar las ocurrencias de un personaje dado en una cadena

// Programa C ++ para encontrar el personaje
// tener la frecuencia más alta en una cadena
#incluir 
#incluir 
#define ASCII_SIZE 256
usando el espacio de nombres std;
char maxFrequencyChar (cadena str)
{
// Matriz para almacenar la frecuencia de cada carácter
// Inicializó la frecuencia de cada carácter como 0
int frecuencia [ASCII_SIZE] = {0};
// Encontrar la longitud de la cadena de entrada
int lenOfStr = str.length ();
// Inicializar la variable maxFrequency
int maxFrequency = -1;
// Inicializar la variable maxFrequencyChar
char maxFrequencyChar;
// Atravesar y mantener el
// frecuencia de cada carácter
para (int i = 0; i {
frecuencia [str [i]] ++;
if (maxFrequency {
maxFrequency = frecuencia [str [i]];
maxFrequencyChar = str [i];
}
}
return maxFrequencyChar;
}
// Código del conductor
int main ()
{
string str1 = "¿Qué bruja es cuál?";
cout << "cadena1:" << cadena1 << endl;
cout << "El carácter de frecuencia más alta es:" << maxFrequencyChar (str1) << endl;
string str2 = "Lanzó tres tiros libres";
cout << "str2:" << str2 << endl;
cout << "El carácter de frecuencia más alta es:" << maxFrequencyChar (str2) << endl;
string str3 = "Eddie lo editó";
cout << "str3:" << str3 << endl;
cout << "El carácter de frecuencia más alta es:" << maxFrequencyChar (str3) << endl;
string str4 = "Makeuseof";
cout << "str4:" << str4 << endl;
cout << "El carácter de frecuencia más alta es:" << maxFrequencyChar (str4) << endl;
string str5 = "Ella ve queso";
cout << "str5:" << str5 << endl;
cout << "El carácter de frecuencia más alta es:" << maxFrequencyChar (str5) << endl;
}

Producción:

str1: ¿Qué bruja es cuál?
El carácter de frecuencia más alta es: h
str2: Lanzó tres tiros libres
El carácter de frecuencia más alta es: e
str3: Eddie lo editó
El carácter de frecuencia más alta es: d
str4: Makeuseof
El carácter de frecuencia más alta es: e
str5: Ella ve queso
El carácter de frecuencia más alta es: e

Programa Python para encontrar el personaje con mayor frecuencia

A continuación se muestra el programa de Python para encontrar el carácter con la frecuencia más alta en una cadena:

Relacionados: Cómo invertir una cadena en C ++, Python y JavaScript

# Programa de Python para encontrar el personaje
# que tiene la frecuencia más alta en una cadena
TAMAÑO_ASCII = 256
def maxFrequencyChar (str):
# Array para almacenar la frecuencia de cada carácter
# Inicializó la frecuencia de cada carácter como 0
frecuencia = [0] * ASCII_SIZE
# Inicializar la variable maxFrequency
maxFrequency = -1
# Inicializar la variable maxFrequencyChar
maxFrequencyChar = ''
# Atravesar y mantener el
# frecuencia de cada carácter
porque yo en str:
frecuencia [ord (i)] + = 1
porque yo en str:
si maxFrequency maxFrequency = frecuencia [ord (i)]
maxFrequencyChar = i
return maxFrequencyChar
# Código del conductor
str1 = "¿Qué bruja es cuál?"
print ("cadena1:", cadena1)
print ("El carácter de frecuencia más alta es:", maxFrequencyChar (str1))
str2 = "Lanzó tres tiros libres"
print ("cadena2:", cadena2)
print ("El carácter de frecuencia más alta es:", maxFrequencyChar (str2))
str3 = "Eddie lo editó"
print ("str3:", str3)
print ("El carácter de frecuencia más alta es:", maxFrequencyChar (str3))
str4 = "Makeuseof"
print ("str4:", str4)
print ("El carácter de frecuencia más alta es:", maxFrequencyChar (str4))
str5 = "Ella ve queso"
print ("str5:", str5)
print ("El carácter de frecuencia más alta es:", maxFrequencyChar (str5))

Producción:

str1: ¿Qué bruja es cuál?
El carácter de frecuencia más alta es: h
str2: Lanzó tres tiros libres
El carácter de frecuencia más alta es: e
str3: Eddie lo editó
El carácter de frecuencia más alta es: d
str4: Makeuseof
El carácter de frecuencia más alta es: e
str5: Ella ve queso
El carácter de frecuencia más alta es: e

Programa C para encontrar el personaje con la frecuencia más alta

A continuación se muestra el programa en C para encontrar el carácter con la frecuencia más alta en una cadena:

Relacionados: Cómo encontrar vocales, consonantes, dígitos y caracteres especiales en una cadena

// Programa en C para encontrar el personaje
// tener la frecuencia más alta en una cadena
#incluir 
#incluir 
#define ASCII_SIZE 256
usando el espacio de nombres std;
char maxFrequencyChar (char * str)
{
// Matriz para almacenar la frecuencia de cada carácter
// Inicializó la frecuencia de cada carácter como 0
int frecuencia [ASCII_SIZE] = {0};
// Encontrar la longitud de la cadena de entrada
int lenOfStr = strlen (str);
// Inicializar la variable maxFrequency
int maxFrequency = 0;
// Inicializar la variable maxFrequencyChar
char maxFrequencyChar;
// Atravesar y mantener el
// frecuencia de cada carácter
para (int i = 0; i {
frecuencia [str [i]] ++;
if (maxFrequency {
maxFrequency = frecuencia [str [i]];
maxFrequencyChar = str [i];
}
}
return maxFrequencyChar;
}
// Código del conductor
int main ()
{
char str1 [] = "¿Qué bruja es cuál?";
printf ("cadena1:% s", cadena1);
printf ("El carácter de frecuencia más alta es:% c \ ⁠n", maxFrequencyChar (str1));
char str2 [] = "Lanzó tres tiros libres";
printf ("cadena2:% s", cadena2);
printf ("El carácter de frecuencia más alta es:% c \ ⁠n", maxFrequencyChar (str2));
char str3 [] = "Eddie lo editó";
printf ("cadena3:% s", cadena3);
printf ("El carácter de frecuencia más alta es:% c \ ⁠n", maxFrequencyChar (str3));
char str4 [] = "Makeuseof";
printf ("str4:% s", str4);
printf ("El carácter de frecuencia más alta es:% c \ ⁠n", maxFrequencyChar (str4));
char str5 [] = "Ella ve queso";
printf ("cadena1:% s", cadena5);
printf ("El carácter de frecuencia más alta es:% c \ ⁠n", maxFrequencyChar (str5));
}

Producción:

str1: ¿Qué bruja es cuál?
El carácter de frecuencia más alta es: h
str2: Lanzó tres tiros libres
El carácter de frecuencia más alta es: e
str3: Eddie lo editó
El carácter de frecuencia más alta es: d
str4: Makeuseof
El carácter de frecuencia más alta es: e
str5: Ella ve queso
El carácter de frecuencia más alta es: e

Programa JavaScript para encontrar el personaje con mayor frecuencia

A continuación se muestra el programa JavaScript para encontrar el carácter con la frecuencia más alta en una cadena:

// programa JavaScript para encontrar el personaje
// tener la frecuencia más alta en una cadena
deje ASCII_SIZE = 256;
función maxFrequencyChar (str)
{
// Matriz para almacenar la frecuencia de cada carácter
// Inicializó la frecuencia de cada carácter como 0
let Frequency = new Array (ASCII_SIZE);
para (sea i = 0; i {
frecuencia [i] = 0;
}
// Encontrar la longitud de la cadena de entrada
let lenOfStr = str.length;
para (sea i = 0; i {
frecuencia [str [i] .charCodeAt (0)] + = 1;
}
// Inicializar la variable maxFrequency
deje maxFrequency = -1;
// Inicializar la variable maxFrequencyChar
let maxFrequencyChar = '';
// Atravesar y mantener el
// frecuencia de cada carácter
para (sea i = 0; i {
if (maxFrequency {
maxFrequency = frecuencia [str [i] .charCodeAt (0)];
maxFrequencyChar = str [i];
}
}
return maxFrequencyChar;
}
// Código del conductor
let str1 = "¿Qué bruja es cuál?";
document.write ("str1:" + str1 + "
");
document.write ("El carácter de frecuencia más alta es:" + maxFrequencyChar (str1) + "
")
let str2 = "Lanzó tres tiros libres";
document.write ("str2:" + str2 + "
");
document.write ("El carácter de frecuencia más alta es:" + maxFrequencyChar (str2) + "
")
let str3 = "Eddie lo editó";
document.write ("str3:" + str3 + "
");
document.write ("El carácter de frecuencia más alta es:" + maxFrequencyChar (str3) + "
")
let str4 = "Makeuseof";
document.write ("str4:" + str4 + "
");
document.write ("El carácter de frecuencia más alta es:" + maxFrequencyChar (str4) + "
")
let str5 = "Ella ve queso";
document.write ("str5:" + str5 + "
");
document.write ("El carácter de frecuencia más alta es:" + maxFrequencyChar (str5) + "
")

Producción:

str1: ¿Qué bruja es cuál?
El carácter de frecuencia más alta es: h
str2: Lanzó tres tiros libres
El carácter de frecuencia más alta es: e
str3: Eddie lo editó
El carácter de frecuencia más alta es: d
str4: Makeuseof
El carácter de frecuencia más alta es: e
str5: Ella ve queso
El carácter de frecuencia más alta es: e

Analizar la complejidad del tiempo y el espacio

La complejidad temporal del maxFrequencyChar () la función es En). La complejidad espacial del maxFrequencyChar () la función es O (1) como un espacio fijo (matriz hash). No depende del tamaño de la cadena de entrada.

La notación Big-O le brinda una forma de calcular cuánto tiempo llevará ejecutar su código. Es uno de los conceptos más importantes para el análisis de algoritmos. Si eres programador, debes conocer la notación Big-O.

Yuvraj Chandra (30 Artículos publicados)

Yuvraj es estudiante de licenciatura en Ciencias de la Computación en la Universidad de Delhi, India. Le apasiona el desarrollo web Full Stack. Cuando no está escribiendo, está explorando la profundidad de diferentes tecnologías.

Más de Yuvraj Chandra