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 dada "Ela vê 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.
Deixe a string de entrada ser "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:
// C++ program to find the character
// having the highest frequency in a string
#include <iostream>
#include <string>
#define ASCII_SIZE 256
using namespace std;
char maxFrequencyChar(string str)
{
// Array to store frequency of each characters
// Initialized the frequency of each character as 0
int frequency[ASCII_SIZE] = {0};
// Finding length of the input string
int lenOfStr = str.length();
// Initialize maxFrequency variable
int maxFrequency = -1;
// Initialize maxFrequencyChar variable
char maxFrequencyChar;
// Traversing and maintaining the
// frequency of each characters
for (int i = 0; i < lenOfStr; i++)
{
frequency[str[i]]++;
if (maxFrequency < frequency[str[i]])
{
maxFrequency = frequency[str[i]];
maxFrequencyChar = str[i];
}
}
return maxFrequencyChar;
}
// Driver Code
int main()
{
string str1 = "Which witch is which?";
cout << "str1: " << str1 << endl;
cout << "The highest frequency character is: " << maxFrequencyChar(str1) << endl;
string str2 = "He threw three free throws";
cout << "str2: " << str2 << endl;
cout << "The highest frequency character is: " << maxFrequencyChar(str2) << endl;
string str3 = "Eddie edited it";
cout << "str3: " << str3 << endl;
cout << "The highest frequency character is: " << maxFrequencyChar(str3) << endl;
string str4 = "Makeuseof";
cout << "str4: " << str4 << endl;
cout << "The highest frequency character is: " << maxFrequencyChar(str4) << endl;
string str5 = "She sees cheese";
cout << "str5: " << str5 << endl;
cout << "The highest frequency character is: " << maxFrequencyChar(str5) << endl;
}
Resultado:
str1: Which witch is which?
The highest frequency character is: h
str2: He threw three free throws
The highest frequency character is: e
str3: Eddie edited it
The highest frequency character is: d
str4: Makeuseof
The highest frequency character is: e
str5: She sees cheese
The highest frequency character is: ePrograma 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:
# Python program to find the character
# having the highest frequency in a string
ASCII_SIZE = 256
def maxFrequencyChar(str):
# Array to store frequency of each characters
# Initialized the frequency of each character as 0
frequency = [0] * ASCII_SIZE
# Initialize maxFrequency variable
maxFrequency = -1
# Initialize maxFrequencyChar variable
maxFrequencyChar = ''
# Traversing and maintaining the
# frequency of each characters
for i in str:
frequency[ord(i)] += 1
for i in str:
if maxFrequency < frequency[ord(i)]:
maxFrequency = frequency[ord(i)]
maxFrequencyChar = i
return maxFrequencyChar
# Driver Code
str1 = "Which witch is which?"
print("str1:", str1)
print("The highest frequency character is:", maxFrequencyChar(str1))
str2 = "He threw three free throws"
print("str2:", str2)
print("The highest frequency character is:", maxFrequencyChar(str2))
str3 = "Eddie edited it"
print("str3:", str3)
print("The highest frequency character is:", maxFrequencyChar(str3))
str4 = "Makeuseof"
print("str4:", str4)
print("The highest frequency character is:", maxFrequencyChar(str4))
str5 = "She sees cheese"
print("str5:", str5)
print("The highest frequency character is:", maxFrequencyChar(str5))
Resultado:
str1: Which witch is which?
The highest frequency character is: h
str2: He threw three free throws
The highest frequency character is: e
str3: Eddie edited it
The highest frequency character is: d
str4: Makeuseof
The highest frequency character is: e
str5: She sees cheese
The highest frequency character is: ePrograma 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:
// C program to find the character
// having the highest frequency in a string
#include <iostream>
#include <cstring>
#define ASCII_SIZE 256
using namespace std;
char maxFrequencyChar(char *str)
{
// Array to store frequency of each characters
// Initialized the frequency of each character as 0
int frequency[ASCII_SIZE] = {0};
// Finding length of the input string
int lenOfStr = strlen(str);
// Initialize maxFrequency variable
int maxFrequency = 0;
// Initialize maxFrequencyChar variable
char maxFrequencyChar;
// Traversing and maintaining the
// frequency of each characters
for (int i = 0; i < lenOfStr; i++)
{
frequency[str[i]]++;
if (maxFrequency < frequency[str[i]])
{
maxFrequency = frequency[str[i]];
maxFrequencyChar = str[i];
}
}
return maxFrequencyChar;
}
// Driver Code
int main()
{
char str1[] = "Which witch is which?";
printf("str1: %s", str1);
printf("The highest frequency character is: %c n", maxFrequencyChar(str1));
char str2[] = "He threw three free throws";
printf("str2: %s", str2);
printf("The highest frequency character is: %c n", maxFrequencyChar(str2));
char str3[] = "Eddie edited it";
printf("str3: %s", str3);
printf("The highest frequency character is: %c n", maxFrequencyChar(str3));
char str4[] = "Makeuseof";
printf("str4: %s", str4);
printf("The highest frequency character is: %c n", maxFrequencyChar(str4));
char str5[] = "She sees cheese";
printf("str1: %s", str5);
printf("The highest frequency character is: %c n", maxFrequencyChar(str5));
}Resultado:
str1: Which witch is which?
The highest frequency character is: h
str2: He threw three free throws
The highest frequency character is: e
str3: Eddie edited it
The highest frequency character is: d
str4: Makeuseof
The highest frequency character is: e
str5: She sees cheese
The highest frequency character is: ePrograma 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:
// JavaScript program to find the character
// having the highest frequency in a string
let ASCII_SIZE = 256;
function maxFrequencyChar(str)
{
// Array to store frequency of each characters
// Initialized the frequency of each character as 0
let frequency = new Array(ASCII_SIZE);
for (let i = 0; i < ASCII_SIZE; i++)
{
frequency[i] = 0;
}
// Finding length of the input string
let lenOfStr = str.length;
for (let i = 0; i < lenOfStr; i++)
{
frequency[str[i].charCodeAt(0)] += 1;
}
// Initialize maxFrequency variable
let maxFrequency = -1;
// Initialize maxFrequencyChar variable
let maxFrequencyChar = '';
// Traversing and maintaining the
// frequency of each characters
for (let i = 0; i < lenOfStr; i++)
{
if (maxFrequency < frequency[str[i].charCodeAt(0)])
{
maxFrequency = frequency[str[i].charCodeAt(0)];
maxFrequencyChar = str[i];
}
}
return maxFrequencyChar;
}
// Driver Code
let str1 = "Which witch is which?";
document.write("str1: " + str1 + "<br>");
document.write("The highest frequency character is: " + maxFrequencyChar(str1) + "<br>")
let str2 = "He threw three free throws";
document.write("str2: " + str2 + "<br>");
document.write("The highest frequency character is: " + maxFrequencyChar(str2) + "<br>")
let str3 = "Eddie edited it";
document.write("str3: " + str3 + "<br>");
document.write("The highest frequency character is: " + maxFrequencyChar(str3) + "<br>")
let str4 = "Makeuseof";
document.write("str4: " + str4 + "<br>");
document.write("The highest frequency character is: " + maxFrequencyChar(str4) + "<br>")
let str5 = "She sees cheese";
document.write("str5: " + str5 + "<br>");
document.write("The highest frequency character is: " + maxFrequencyChar(str5) + "<br>")Resultado:
str1: Which witch is which?
The highest frequency character is: h
str2: He threw three free throws
The highest frequency character is: e
str3: Eddie edited it
The highest frequency character is: d
str4: Makeuseof
The highest frequency character is: e
str5: She sees cheese
The highest frequency character is: eAnalise a complexidade do tempo e do espaço
A complexidade de tempo da função maxFrequencyChar () é O (n) . A complexidade de espaço da função maxFrequencyChar () é 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.
