Come trovare il carattere che ricorre più frequentemente in una stringa

Le stringhe sono un argomento molto importante nella programmazione delle interviste. È saggio esercitarsi su alcuni problemi di programmazione incentrati sulle stringhe prima delle interviste. In questo articolo imparerai come trovare il carattere che ricorre più frequentemente in una stringa.

Esempi per comprendere il problema

Esempio 1: Lascia che la stringa data sia "Makeuseof". Il carattere 'e' si verifica 2 volte nella stringa data e tutti gli altri caratteri si verificano solo una volta. Pertanto, il carattere 'e' ha la frequenza più alta nella stringa data.

Esempio 2: Lascia che la stringa data sia "Lei vede il formaggio". Il carattere 'e' si verifica 6 volte nella stringa data e tutti gli altri caratteri si verificano meno di 6 volte. Pertanto, il carattere 'e' ha la frequenza più alta nella stringa data.

Approccio per trovare il carattere che ricorre più frequentemente in una stringa

La tecnica di hashing è il modo più efficiente per trovare il carattere con la frequenza più alta in una stringa. In questa tecnica, la stringa viene attraversata e ogni carattere della stringa viene sottoposto a hash in un array di caratteri ASCII.

Lascia che la stringa di input sia "Makeuseof", ogni carattere di questa stringa viene hash come segue:

frequenza['M'] = 1

frequenza['a] = 1

frequenza['k'] = 1

frequenza['e'] = 2

frequenza['u'] = 1

frequenza['s'] = 1

frequenza['o'] = 1

frequenza['f'] = 1

Viene restituito l'indice del valore massimo nell'array di frequenza. Qui 2 è il valore più alto, quindi viene restituita 'e'.

Programma C++ per trovare il carattere con la frequenza più alta

Di seguito è riportato il programma C++ per trovare il carattere con la frequenza più alta in una stringa:

Relazionato: Come contare le occorrenze di un dato carattere in una stringa

// Programma C++ per trovare il carattere
// ha la frequenza più alta in una stringa
#includere 
#includere 
#define ASCII_SIZE 256
usando lo spazio dei nomi std;
char maxFrequencyChar (stringa str)
{
// Array per memorizzare la frequenza di ciascun carattere
// Inizializzato la frequenza di ogni carattere come 0
int frequenza[ASCII_SIZE] = {0};
// Trovare la lunghezza della stringa di input
int lenOfStr = str.length();
// Inizializza la variabile maxFrequency
int maxFrequency = -1;
// Inizializza la variabile maxFrequencyChar
char maxFrequencyChar;
// Attraversare e mantenere il
// frequenza di ogni carattere
per (int i = 0; i < lenOfStr; io++)
{
frequenza[str[i]]++;
if (maxFrequency < frequency[str[i]])
{
maxFrequency = frequenza[str[i]];
maxFrequencyChar = str[i];
}
}
restituisce maxFrequencyChar;
}
// Codice conducente
intero principale()
{
string str1 = "Quale strega è quale?";
cout << "str1: " << str1 << endl;
cout << "Il carattere di frequenza più alta è: " << maxFrequencyChar (str1) << endl;
string str2 = "Ha tirato tre tiri liberi";
cout << "str2: " << str2 << endl;
cout << "Il carattere di frequenza più alta è: " << maxFrequencyChar (str2) << endl;
string str3 = "Eddie l'ha modificato";
cout << "str3: " << str3 << endl;
cout << "Il carattere di frequenza più alta è: " << maxFrequencyChar (str3) << endl;
string str4 = "Makeuseof";
cout << "str4: " << str4 << endl;
cout << "Il carattere di frequenza più alta è: " << maxFrequencyChar (str4) << endl;
string str5 = "Lei vede il formaggio";
cout << "str5: " << str5 << endl;
cout << "Il carattere di frequenza più alta è: " << maxFrequencyChar (str5) << endl;
}

Produzione:

str1: Quale strega è quale?
Il carattere di frequenza più alta è: h
str2: Ha tirato tre tiri liberi
Il carattere di frequenza più alta è: e
str3: Eddie l'ha modificato
Il carattere di frequenza più alta è: d
str4: Makeuseof
Il carattere di frequenza più alta è: e
str5: Lei vede il formaggio
Il carattere di frequenza più alta è: e

Programma Python per trovare il personaggio con la frequenza più alta

Di seguito è riportato il programma Python per trovare il carattere con la frequenza più alta in una stringa:

Relazionato: Come invertire una stringa in C++, Python e JavaScript

# Programma Python per trovare il personaggio
# che ha la frequenza più alta in una stringa
ASCII_SIZE = 256
def maxFrequencyChar (str):
# Array per memorizzare la frequenza di ciascun carattere
# Inizializzato la frequenza di ogni carattere come 0
frequenza = [0] * ASCII_SIZE
# Inizializza la variabile maxFrequency
Frequenza massima = -1
# Inizializza la variabile maxFrequencyChar
maxFrequencyChar = ''
# Attraversare e mantenere il
# frequenza di ogni carattere
per io in str:
frequenza[ord (i)] += 1
per io in str:
se maxFrequency < frequency[ord (i)]:
maxFrequency = frequency[ord (i)]
maxFrequencyChar = i
restituisce maxFrequencyChar
# Codice conducente
str1 = "Quale strega è quale?"
print("str1:", str1)
print("Il carattere di frequenza più alta è:", maxFrequencyChar (str1))
str2 = "Ha tirato tre tiri liberi"
print("str2:", str2)
print("Il carattere di frequenza più alta è:", maxFrequencyChar (str2))
str3 = "Eddie l'ha modificato"
print("str3:", str3)
print("Il carattere di frequenza più alta è:", maxFrequencyChar (str3))
str4 = "Sfruttamento di"
print("str4:", str4)
print("Il carattere di frequenza più alta è:", maxFrequencyChar (str4))
str5 = "Lei vede il formaggio"
print("str5:", str5)
print("Il carattere di frequenza più alta è:", maxFrequencyChar (str5))

Produzione:

str1: Quale strega è quale?
Il carattere di frequenza più alta è: h
str2: Ha tirato tre tiri liberi
Il carattere di frequenza più alta è: e
str3: Eddie l'ha modificato
Il carattere di frequenza più alta è: d
str4: Makeuseof
Il carattere di frequenza più alta è: e
str5: Lei vede il formaggio
Il carattere di frequenza più alta è: e

Programma C per trovare il personaggio con la frequenza più alta

Di seguito è riportato il programma C per trovare il carattere con la frequenza più alta in una stringa:

Relazionato: Come trovare vocali, consonanti, cifre e caratteri speciali in una stringa

// programma C per trovare il carattere
// ha la frequenza più alta in una stringa
#includere 
#includere 
#define ASCII_SIZE 256
usando lo spazio dei nomi std;
char maxFrequencyChar (char *str)
{
// Array per memorizzare la frequenza di ciascun carattere
// Inizializzato la frequenza di ogni carattere come 0
int frequenza[ASCII_SIZE] = {0};
// Trovare la lunghezza della stringa di input
int lenOfStr = strlen (str);
// Inizializza la variabile maxFrequency
int maxFrequency = 0;
// Inizializza la variabile maxFrequencyChar
char maxFrequencyChar;
// Attraversare e mantenere il
// frequenza di ogni carattere
per (int i = 0; i < lenOfStr; io++)
{
frequenza[str[i]]++;
if (maxFrequency < frequency[str[i]])
{
maxFrequency = frequenza[str[i]];
maxFrequencyChar = str[i];
}
}
restituisce maxFrequencyChar;
}
// Codice conducente
intero principale()
{
char str1[] = "Quale strega è quale?";
printf("str1: %s", str1);
printf("Il carattere di frequenza più alta è: %c \⁠n", maxFrequencyChar (str1));
char str2[] ​​= "Ha tirato tre tiri liberi";
printf("str2: %s", str2);
printf("Il carattere di frequenza più alta è: %c \⁠n", maxFrequencyChar (str2));
char str3[] = "Eddie l'ha modificato";
printf("str3: %s", str3);
printf("Il carattere di frequenza più alta è: %c \⁠n", maxFrequencyChar (str3));
char str4[] = "Makeuseof";
printf("str4: %s", str4);
printf("Il carattere di frequenza più alta è: %c \⁠n", maxFrequencyChar (str4));
char str5[] = "Lei vede il formaggio";
printf("str1: %s", str5);
printf("Il carattere di frequenza più alta è: %c \⁠n", maxFrequencyChar (str5));
}

Produzione:

str1: Quale strega è quale?
Il carattere di frequenza più alta è: h
str2: Ha tirato tre tiri liberi
Il carattere di frequenza più alta è: e
str3: Eddie l'ha modificato
Il carattere di frequenza più alta è: d
str4: Makeuseof
Il carattere di frequenza più alta è: e
str5: Lei vede il formaggio
Il carattere di frequenza più alta è: e

Programma JavaScript per trovare il carattere con la frequenza più alta

Di seguito è riportato il programma JavaScript per trovare il carattere con la frequenza più alta in una stringa:

// Programma JavaScript per trovare il carattere
// ha la frequenza più alta in una stringa
let ASCII_SIZE = 256;
funzione maxFrequencyChar (str)
{
// Array per memorizzare la frequenza di ciascun carattere
// Inizializzato la frequenza di ogni carattere come 0
let frequency = new Array (ASCII_SIZE);
per (lascia i = 0; i < ASCII_SIZE; io++)
{
frequenza[i] = 0;
}
// Trovare la lunghezza della stringa di input
let lenOfStr = str.lunghezza;
per (lascia i = 0; i < lenOfStr; io++)
{
frequenza[str[i].charCodeAt (0)] += 1;
}
// Inizializza la variabile maxFrequency
let maxFrequency = -1;
// Inizializza la variabile maxFrequencyChar
let maxFrequencyChar = '';
// Attraversare e mantenere il
// frequenza di ogni carattere
per (lascia i = 0; i < lenOfStr; io++)
{
if (maxFrequency < frequency[str[i].charCodeAt (0)])
{
maxFrequency = frequency[str[i].charCodeAt (0)];
maxFrequencyChar = str[i];
}
}
restituisce maxFrequencyChar;
}
// Codice conducente
let str1 = "Quale strega è quale?";
document.write("str1: " + str1 + "
");
document.write("Il carattere di frequenza più alta è: " + maxFrequencyChar (str1) + "
")
let str2 = "Ha tirato tre tiri liberi";
document.write("str2: " + str2 + "
");
document.write("Il carattere di frequenza più alta è: " + maxFrequencyChar (str2) + "
")
let str3 = "Eddie l'ha modificato";
document.write("str3: " + str3 + "
");
document.write("Il carattere di frequenza più alta è: " + maxFrequencyChar (str3) + "
")
let str4 = "Makeuseof";
document.write("str4: " + str4 + "
");
document.write("Il carattere di frequenza più alta è: " + maxFrequencyChar (str4) + "
")
let str5 = "Lei vede il formaggio";
document.write("str5: " + str5 + "
");
document.write("Il carattere di frequenza più alta è: " + maxFrequencyChar (str5) + "
")

Produzione:

str1: Quale strega è quale?
Il carattere di frequenza più alta è: h
str2: Ha tirato tre tiri liberi
Il carattere di frequenza più alta è: e
str3: Eddie l'ha modificato
Il carattere di frequenza più alta è: d
str4: Makeuseof
Il carattere di frequenza più alta è: e
str5: Lei vede il formaggio
Il carattere di frequenza più alta è: e

Analizzare la complessità del tempo e dello spazio

La complessità temporale del maxFrequencyChar() la funzione è Sopra). La complessità spaziale del maxFrequencyChar() la funzione è O(1) come uno spazio fisso (array hash). Non dipende dalla dimensione della stringa di input.

La notazione Big-O ti dà un modo per calcolare quanto tempo ci vorrà per eseguire il tuo codice. È uno dei concetti più importanti per l'analisi degli algoritmi. Se sei un programmatore, devi conoscere la notazione Big-O.

Yuvraj Chandra (30 articoli pubblicati)

Yuvraj è uno studente universitario di Informatica presso l'Università di Delhi, in India. È appassionato di sviluppo Web Full Stack. Quando non scrive, esplora la profondità di diverse tecnologie.

Altro da Yuvraj Chandra