Como encontrar o caractere que ocorre com mais frequência em uma string

Strings são um tópico muito importante em entrevistas de programação. É aconselhável praticar alguns problemas de programação focados em strings antes de suas entrevistas. Neste artigo, você aprenderá como localizar o caractere que ocorre com mais frequência em uma string.

Exemplos para compreender o problema

Exemplo 1: Seja a string fornecida "Makeuseof". O caractere 'e' ocorre 2 vezes na string fornecida e todos os outros caracteres ocorrem apenas uma vez. Assim, o caractere 'e' tem a frequência mais alta na string fornecida.

Exemplo 2: Seja a string fornecida "Ela vê o queijo". O caractere 'e' ocorre 6 vezes na string fornecida e todos os outros caracteres ocorrem menos de 6 vezes. Assim, o caractere 'e' tem a frequência mais alta na string fornecida.

Abordagem para encontrar o caractere que ocorre com mais frequência em uma string

A técnica de hashing é a maneira mais eficiente de encontrar o caractere com a frequência mais alta em uma string. Nesta técnica, a string é percorrida e cada caractere da string é misturado em uma matriz de caracteres ASCII.

Seja a string de entrada "Makeuseof", cada caractere dessa string é hash como segue:

frequência ['M'] = 1

frequência ['a] = 1

frequência ['k'] = 1

frequência ['e'] = 2

frequência ['u'] = 1

frequência ['s'] = 1

frequência ['o'] = 1

frequência ['f'] = 1

O índice do valor máximo na matriz de frequência é retornado. Aqui 2 é o valor mais alto, portanto, 'e' é retornado.

Programa C ++ para encontrar o personagem com a maior frequência

Abaixo está o programa C ++ para encontrar o caractere com a maior frequência em uma string:

Relacionado: Como contar as ocorrências de um determinado caractere em uma string

// Programa C ++ para encontrar o personagem
// tendo a maior frequência em uma string
#incluir 
#incluir 
# define ASCII_SIZE 256
usando namespace std;
char maxFrequencyChar (string str)
{
// Matriz para armazenar a frequência de cada personagem
// Inicializou a frequência de cada caractere como 0
frequência interna [ASCII_SIZE] = {0};
// Encontrando o comprimento da string de entrada
int lenOfStr = str.length ();
// Inicializar a variável maxFrequency
int maxFrequency = -1;
// Inicializar a variável maxFrequencyChar
char maxFrequencyChar;
// Atravessando e mantendo o
// frequência de cada personagem
para (int i = 0; i {
frequência [str [i]] ++;
if (maxFrequency {
maxFrequency = frequência [str [i]];
maxFrequencyChar = str [i];
}
}
return maxFrequencyChar;
}
// Código do driver
int main ()
{
string str1 = "Qual bruxa é qual?";
cout << "str1:" << str1 << endl;
cout << "O caractere de frequência mais alta é:" << maxFrequencyChar (str1) << endl;
string str2 = "Ele lançou três lances livres";
cout << "str2:" << str2 << endl;
cout << "O caractere de frequência mais alta é:" << maxFrequencyChar (str2) << endl;
string str3 = "Eddie editou";
cout << "str3:" << str3 << endl;
cout << "O caractere de frequência mais alta é:" << maxFrequencyChar (str3) << endl;
string str4 = "Makeuseof";
cout << "str4:" << str4 << endl;
cout << "O caractere de frequência mais alta é:" << maxFrequencyChar (str4) << endl;
string str5 = "Ela vê queijo";
cout << "str5:" << str5 << endl;
cout << "O caractere de frequência mais alta é:" << maxFrequencyChar (str5) << endl;
}

Resultado:

str1: Qual bruxa é qual?
O caractere de frequência mais alta é: h
str2: Ele lançou três lances livres
O caractere de frequência mais alta é: e
str3: Eddie editou
O caractere de frequência mais alta é: d
str4: Makeuseof
O caractere de frequência mais alta é: e
str5: Ela vê queijo
O caractere de frequência mais alta é: e

Programa Python para encontrar o personagem com a maior frequência

Abaixo está o programa Python para encontrar o caractere com a maior frequência em uma string:

Relacionado: Como reverter uma string em C ++, Python e JavaScript

# Programa Python para encontrar o personagem
# tendo a frequência mais alta em uma string
ASCII_SIZE = 256
def maxFrequencyChar (str):
# Array para armazenar a frequência de cada personagem
# Inicializou a frequência de cada caractere como 0
frequência = [0] * ASCII_SIZE
# Initialize a variável maxFrequency
maxFrequency = -1
# Initialize a variável maxFrequencyChar
maxFrequencyChar = ''
# Atravessar e manter o
# frequência de cada personagem
para i em str:
frequência [ord (i)] + = 1
para i em str:
se maxFrequency maxFrequency = frequência [ord (i)]
maxFrequencyChar = i
return maxFrequencyChar
# Código do Driver
str1 = "Qual bruxa é qual?"
imprimir ("str1:", str1)
print ("O caractere de frequência mais alta é:", maxFrequencyChar (str1))
str2 = "Ele lançou três lances livres"
imprimir ("str2:", str2)
print ("O caractere de frequência mais alta é:", maxFrequencyChar (str2))
str3 = "Eddie editou"
imprimir ("str3:", str3)
print ("O caractere de frequência mais alta é:", maxFrequencyChar (str3))
str4 = "Makeuseof"
imprimir ("str4:", str4)
print ("O caractere de frequência mais alta é:", maxFrequencyChar (str4))
str5 = "Ela vê queijo"
imprimir ("str5:", str5)
print ("O caractere de frequência mais alta é:", maxFrequencyChar (str5))

Resultado:

str1: Qual bruxa é qual?
O caractere de frequência mais alta é: h
str2: Ele lançou três lances livres
O caractere de frequência mais alta é: e
str3: Eddie editou
O caractere de frequência mais alta é: d
str4: Makeuseof
O caractere de frequência mais alta é: e
str5: Ela vê queijo
O caractere de frequência mais alta é: e

Programa C para encontrar o personagem com a maior frequência

Abaixo está o programa C para encontrar o caractere com a maior frequência em uma string:

Relacionado: Como encontrar vogais, consoantes, dígitos e caracteres especiais em uma string

// programa C para encontrar o personagem
// tendo a maior frequência em uma string
#incluir 
#incluir 
# define ASCII_SIZE 256
usando namespace std;
char maxFrequencyChar (char * str)
{
// Matriz para armazenar a frequência de cada personagem
// Inicializou a frequência de cada caractere como 0
frequência interna [ASCII_SIZE] = {0};
// Encontrando o comprimento da string de entrada
int lenOfStr = strlen (str);
// Inicializar a variável maxFrequency
int maxFrequency = 0;
// Inicializar a variável maxFrequencyChar
char maxFrequencyChar;
// Atravessando e mantendo o
// frequência de cada personagem
para (int i = 0; i {
frequência [str [i]] ++;
if (maxFrequency {
maxFrequency = frequência [str [i]];
maxFrequencyChar = str [i];
}
}
return maxFrequencyChar;
}
// Código do driver
int main ()
{
char str1 [] = "Qual bruxa é qual?";
printf ("str1:% s", str1);
printf ("O caractere de frequência mais alta é:% c \ ⁠n", maxFrequencyChar (str1));
char str2 [] = "Ele lançou três lances livres";
printf ("str2:% s", str2);
printf ("O caractere de frequência mais alta é:% c \ ⁠n", maxFrequencyChar (str2));
char str3 [] = "Eddie editou";
printf ("str3:% s", str3);
printf ("O caractere de frequência mais alta é:% c \ ⁠n", maxFrequencyChar (str3));
char str4 [] = "Makeuseof";
printf ("str4:% s", str4);
printf ("O caractere de frequência mais alta é:% c \ ⁠n", maxFrequencyChar (str4));
char str5 [] = "Ela vê queijo";
printf ("str1:% s", str5);
printf ("O caractere de frequência mais alta é:% c \ ⁠n", maxFrequencyChar (str5));
}

Resultado:

str1: Qual bruxa é qual?
O caractere de frequência mais alta é: h
str2: Ele lançou três lances livres
O caractere de frequência mais alta é: e
str3: Eddie editou
O caractere de frequência mais alta é: d
str4: Makeuseof
O caractere de frequência mais alta é: e
str5: Ela vê queijo
O caractere de frequência mais alta é: e

Programa JavaScript para encontrar o personagem com a maior frequência

Abaixo está o programa JavaScript para encontrar o caractere com a maior frequência em uma string:

// Programa JavaScript para encontrar o personagem
// tendo a maior frequência em uma string
deixe ASCII_SIZE = 256;
função maxFrequencyChar (str)
{
// Matriz para armazenar a frequência de cada personagem
// Inicializou a frequência de cada caractere como 0
deixe frequência = novo Array (ASCII_SIZE);
para (deixe i = 0; i {
frequência [i] = 0;
}
// Encontrando o comprimento da string de entrada
deixe lenOfStr = str.length;
para (deixe i = 0; i {
frequência [str [i] .charCodeAt (0)] + = 1;
}
// Inicializar a variável maxFrequency
deixe maxFrequency = -1;
// Inicializar a variável maxFrequencyChar
let maxFrequencyChar = '';
// Atravessando e mantendo o
// frequência de cada personagem
para (deixe i = 0; i {
if (maxFrequency {
maxFrequency = frequência [str [i] .charCodeAt (0)];
maxFrequencyChar = str [i];
}
}
return maxFrequencyChar;
}
// Código do driver
let str1 = "Qual bruxa é qual?";
document.write ("str1:" + str1 + "
");
document.write ("O caractere de frequência mais alta é:" + maxFrequencyChar (str1) + "
")
deixe str2 = "Ele lançou três lances livres";
document.write ("str2:" + str2 + "
");
document.write ("O caractere de frequência mais alta é:" + maxFrequencyChar (str2) + "
")
let str3 = "Eddie editou";
document.write ("str3:" + str3 + "
");
document.write ("O caractere de frequência mais alta é:" + maxFrequencyChar (str3) + "
")
let str4 = "Makeuseof";
document.write ("str4:" + str4 + "
");
document.write ("O caractere de frequência mais alta é:" + maxFrequencyChar (str4) + "
")
let str5 = "Ela vê queijo";
document.write ("str5:" + str5 + "
");
document.write ("O caractere de frequência mais alta é:" + maxFrequencyChar (str5) + "
")

Resultado:

str1: Qual bruxa é qual?
O caractere de frequência mais alta é: h
str2: Ele lançou três lances livres
O caractere de frequência mais alta é: e
str3: Eddie editou
O caractere de frequência mais alta é: d
str4: Makeuseof
O caractere de frequência mais alta é: e
str5: Ela vê queijo
O caractere de frequência mais alta é: e

Analise a complexidade do tempo e do espaço

A complexidade do tempo do maxFrequencyChar () função é Sobre). A complexidade do espaço do maxFrequencyChar () função é O (1) como um espaço fixo (array Hash). Não depende do tamanho da string de entrada.

A notação Big-O fornece uma maneira de calcular quanto tempo levará para executar seu código. É um dos conceitos mais importantes para a análise de algoritmos. Se você é um programador, deve conhecer o Big-O Notation.

Yuvraj Chandra (30 artigos publicados)

Yuvraj é estudante de graduação em Ciência da Computação na Universidade de Delhi, na Índia. Ele é apaixonado por Full Stack Web Development. Quando não está escrevendo, ele está explorando a profundidade de diferentes tecnologias.

Mais de Yuvraj Chandra