Comment trouver le caractère le plus fréquent dans une chaîne

Les cordes sont un sujet très important dans la programmation des interviews. Il est sage de pratiquer quelques problèmes de programmation axés sur les chaînes avant vos interviews. Dans cet article, vous apprendrez à rechercher le caractère le plus fréquent dans une chaîne.

Exemples pour comprendre le problème

Exemple 1: Soit la chaîne donnée "Makeuseof". Le caractère 'e' apparaît 2 fois dans la chaîne donnée et tous les autres caractères n'apparaissent qu'une seule fois. Ainsi, le caractère 'e' a la fréquence la plus élevée dans la chaîne donnée.

Exemple 2: Soit la chaîne donnée "Elle voit du fromage". Le caractère 'e' apparaît 6 fois dans la chaîne donnée et tous les autres caractères apparaissent moins de 6 fois. Ainsi, le caractère 'e' a la fréquence la plus élevée dans la chaîne donnée.

Approche pour rechercher le caractère le plus fréquent dans une chaîne

La technique de hachage est le moyen le plus efficace de trouver le caractère ayant la fréquence la plus élevée dans une chaîne. Dans cette technique, la chaîne est parcourue et chaque caractère de la chaîne est haché dans un tableau de caractères ASCII.

Soit la chaîne d'entrée "Makeuseof", chaque caractère de cette chaîne est haché comme suit:

fréquence['M'] = 1

fréquence['a] = 1

fréquence['k'] = 1

fréquence['e'] = 2

fréquence['u'] = 1

fréquence['s'] = 1

fréquence['o'] = 1

fréquence['f'] = 1

L'index de la valeur maximale dans le tableau de fréquences est renvoyé. Ici 2 est la valeur la plus élevée, donc 'e' est renvoyé.

Programme C++ pour trouver le caractère avec la fréquence la plus élevée

Ci-dessous se trouve le programme C++ pour trouver le caractère avec la fréquence la plus élevée dans une chaîne:

En rapport: Comment compter les occurrences d'un caractère donné dans une chaîne

// Programme C++ pour trouver le caractère
// ayant la fréquence la plus élevée dans une chaîne
#inclure 
#inclure 
#define ASCII_SIZE 256
en utilisant l'espace de noms std ;
char maxFrequencyChar (chaîne str)
{
// Tableau pour stocker la fréquence de chaque caractère
// Initialisation de la fréquence de chaque caractère à 0
int fréquence[ASCII_SIZE] = {0};
// Recherche de la longueur de la chaîne d'entrée
int lenOfStr = str.length();
// Initialiser la variable maxFrequency
int maxFrequency = -1;
// Initialiser la variable maxFrequencyChar
char maxFrequencyChar;
// Parcours et maintien du
// fréquence de chaque caractère
pour (entier i = 0; i < lenOfStr; je++)
{
fréquence[str[i]]++ ;
if (maxFrequency < fréquence[str[i]])
{
maxFréquence = fréquence[str[i]] ;
maxFrequencyChar = str[i];
}
}
return maxFrequencyChar;
}
// Code du pilote
int main()
{
string str1 = "Quelle est laquelle ?";
cout << "str1: " << str1 << endl;
cout << "Le caractère de fréquence la plus élevée est: " << maxFrequencyChar (str1) << endl;
string str2 = "Il a lancé trois lancers francs";
cout << "str2: " << str2 << endl;
cout << "Le caractère de fréquence la plus élevée est: " << maxFrequencyChar (str2) << endl;
string str3 = "Eddie l'a édité" ;
cout << "str3: " << str3 << endl;
cout << "Le caractère de fréquence la plus élevée est: " << maxFrequencyChar (str3) << endl;
string str4 = "Makeuseof" ;
cout << "str4: " << str4 << endl;
cout << "Le caractère de fréquence la plus élevée est: " << maxFrequencyChar (str4) << endl;
string str5 = "Elle voit du fromage";
cout << "str5: " << str5 << endl;
cout << "Le caractère de fréquence la plus élevée est: " << maxFrequencyChar (str5) << endl;
}

Production:

str1: Quelle sorcière est laquelle ?
Le caractère de fréquence la plus élevée est: h
str2: Il a lancé trois lancers francs
Le caractère de fréquence la plus élevée est: e
str3: Eddie l'a édité
Le caractère de fréquence la plus élevée est: d
str4: Makeuseof
Le caractère de fréquence la plus élevée est: e
str5: Elle voit du fromage
Le caractère de fréquence la plus élevée est: e

Programme Python pour trouver le caractère avec la fréquence la plus élevée

Vous trouverez ci-dessous le programme Python pour trouver le caractère avec la fréquence la plus élevée dans une chaîne:

En rapport: Comment inverser une chaîne en C++, Python et JavaScript

# Programme Python pour trouver le caractère
# ayant la fréquence la plus élevée dans une chaîne
TAILLE_ASCII = 256
def maxFrequencyChar (str):
# Tableau pour stocker la fréquence de chaque caractère
# Initialisé la fréquence de chaque caractère à 0
fréquence = [0] * ASCII_SIZE
# Initialiser la variable maxFrequency
maxFréquence = -1
# Initialiser la variable maxFrequencyChar
maxFrequencyChar = ''
# Parcourir et entretenir le
# fréquence de chaque caractère
pour i dans str :
fréquence[ord (i)] += 1
pour i dans str :
si maxFréquence < fréquence[ord (i)] :
maxFrequency = fréquence[ord (i)]
maxFrequencyChar = i
retourner maxFrequencyChar
# Code du pilote
str1 = "Quelle est laquelle ?"
print("str1:", str1)
print("Le caractère de fréquence la plus élevée est :", maxFrequencyChar (str1))
str2 = "Il a lancé trois lancers francs"
print("str2:", str2)
print("Le caractère de fréquence la plus élevée est :", maxFrequencyChar (str2))
str3 = "Eddie l'a édité"
print("str3:", str3)
print("Le caractère de fréquence la plus élevée est :", maxFrequencyChar (str3))
str4 = "Makeuseof"
print("str4:", str4)
print("Le caractère de fréquence la plus élevée est :", maxFrequencyChar (str4))
str5 = "Elle voit du fromage"
print("str5:", str5)
print("Le caractère de fréquence la plus élevée est :", maxFrequencyChar (str5))

Production:

str1: Quelle sorcière est laquelle ?
Le caractère de fréquence la plus élevée est: h
str2: Il a lancé trois lancers francs
Le caractère de fréquence la plus élevée est: e
str3: Eddie l'a édité
Le caractère de fréquence la plus élevée est: d
str4: Makeuseof
Le caractère de fréquence la plus élevée est: e
str5: Elle voit du fromage
Le caractère de fréquence la plus élevée est: e

C Programme pour trouver le caractère avec la fréquence la plus élevée

Ci-dessous se trouve le programme C pour trouver le caractère avec la fréquence la plus élevée dans une chaîne:

En rapport: Comment trouver des voyelles, des consonnes, des chiffres et des caractères spéciaux dans une chaîne

// Programme C pour trouver le caractère
// ayant la fréquence la plus élevée dans une chaîne
#inclure 
#inclure 
#define ASCII_SIZE 256
en utilisant l'espace de noms std ;
char maxFrequencyChar (char *str)
{
// Tableau pour stocker la fréquence de chaque caractère
// Initialisation de la fréquence de chaque caractère à 0
int fréquence[ASCII_SIZE] = {0};
// Recherche de la longueur de la chaîne d'entrée
int lenOfStr = strlen (str);
// Initialiser la variable maxFrequency
int maxFréquence = 0 ;
// Initialiser la variable maxFrequencyChar
char maxFrequencyChar;
// Parcours et maintien du
// fréquence de chaque caractère
pour (entier i = 0; i < lenOfStr; je++)
{
fréquence[str[i]]++ ;
if (maxFrequency < fréquence[str[i]])
{
maxFréquence = fréquence[str[i]] ;
maxFrequencyChar = str[i];
}
}
return maxFrequencyChar;
}
// Code du pilote
int main()
{
char str1[] = "Quelle est laquelle ?";
printf("str1: %s", str1) ;
printf("Le caractère de fréquence la plus élevée est: %c \⁠n", maxFrequencyChar (str1));
char str2[] ​​= "Il a lancé trois lancers francs" ;
printf("str2: %s", str2) ;
printf("Le caractère de fréquence la plus élevée est: %c \⁠n", maxFrequencyChar (str2));
char str3[] = "Eddie l'a édité";
printf("str3: %s", str3) ;
printf("Le caractère de fréquence la plus élevée est: %c \⁠n", maxFrequencyChar (str3));
char str4[] = "Makeuseof";
printf("str4: %s", str4) ;
printf("Le caractère de fréquence la plus élevée est: %c \⁠n", maxFrequencyChar (str4));
char str5[] = "Elle voit du fromage";
printf("str1: %s", str5) ;
printf("Le caractère de fréquence la plus élevée est: %c \⁠n", maxFrequencyChar (str5));
}

Production:

str1: Quelle sorcière est laquelle ?
Le caractère de fréquence la plus élevée est: h
str2: Il a lancé trois lancers francs
Le caractère de fréquence la plus élevée est: e
str3: Eddie l'a édité
Le caractère de fréquence la plus élevée est: d
str4: Makeuseof
Le caractère de fréquence la plus élevée est: e
str5: Elle voit du fromage
Le caractère de fréquence la plus élevée est: e

Programme JavaScript pour trouver le caractère avec la fréquence la plus élevée

Vous trouverez ci-dessous le programme JavaScript pour trouver le caractère avec la fréquence la plus élevée dans une chaîne:

// Programme JavaScript pour trouver le caractère
// ayant la fréquence la plus élevée dans une chaîne
laissez ASCII_SIZE = 256 ;
fonction maxFrequencyChar (str)
{
// Tableau pour stocker la fréquence de chaque caractère
// Initialisation de la fréquence de chaque caractère à 0
let fréquence = nouveau tableau (ASCII_SIZE);
pour (soit i = 0; i < ASCII_SIZE; je++)
{
fréquence[i] = 0;
}
// Recherche de la longueur de la chaîne d'entrée
laissez lenOfStr = str.length;
pour (soit i = 0; i < lenOfStr; je++)
{
fréquence[str[i].charCodeAt (0)] += 1;
}
// Initialiser la variable maxFrequency
laissez maxFrequency = -1;
// Initialiser la variable maxFrequencyChar
let maxFrequencyChar = '';
// Parcours et maintien du
// fréquence de chaque caractère
pour (soit i = 0; i < lenOfStr; je++)
{
if (maxFrequency < fréquence[str[i].charCodeAt (0)])
{
maxFrequency = fréquence[str[i].charCodeAt (0)] ;
maxFrequencyChar = str[i];
}
}
return maxFrequencyChar;
}
// Code du pilote
let str1 = "Quelle est laquelle ?";
document.write("str1: " + str1 + "
");
document.write("Le caractère de fréquence la plus élevée est: " + maxFrequencyChar (str1) + "
")
let str2 = "Il a lancé trois lancers francs" ;
document.write("str2: " + str2 + "
");
document.write("Le caractère de fréquence la plus élevée est: " + maxFrequencyChar (str2) + "
")
let str3 = "Eddie l'a édité" ;
document.write("str3: " + str3 + "
");
document.write("Le caractère de fréquence la plus élevée est: " + maxFrequencyChar (str3) + "
")
let str4 = "Makeuseof" ;
document.write("str4: " + str4 + "
");
document.write("Le caractère de fréquence la plus élevée est: " + maxFrequencyChar (str4) + "
")
let str5 = "Elle voit du fromage";
document.write("str5: " + str5 + "
");
document.write("Le caractère de fréquence la plus élevée est: " + maxFrequencyChar (str5) + "
")

Production:

str1: Quelle sorcière est laquelle ?
Le caractère de fréquence la plus élevée est: h
str2: Il a lancé trois lancers francs
Le caractère de fréquence la plus élevée est: e
str3: Eddie l'a édité
Le caractère de fréquence la plus élevée est: d
str4: Makeuseof
Le caractère de fréquence la plus élevée est: e
str5: Elle voit du fromage
Le caractère de fréquence la plus élevée est: e

Analyser la complexité temporelle et spatiale

La complexité temporelle du maxFrequencyChar() la fonction est Au). La complexité spatiale du maxFrequencyChar() la fonction est O(1) comme un espace fixe (tableau de hachage). Cela ne dépend pas de la taille de la chaîne d'entrée.

La notation Big-O vous permet de calculer combien de temps il faudra pour exécuter votre code. C'est l'un des concepts les plus importants pour l'analyse des algorithmes. Si vous êtes programmeur, vous devez connaître Big-O Notation.

Yuvraj Chandra (30 articles publiés)

Yuvraj est un étudiant de premier cycle en informatique à l'Université de Delhi, en Inde. Il est passionné par le développement Web Full Stack. Quand il n'écrit pas, il explore la profondeur de différentes technologies.

Plus de Yuvraj Chandra