Hvordan finne den hyppigst forekommende karakteren i en streng

Strenger er et veldig viktig tema i programmeringsintervjuer. Det er lurt å øve på noen programmeringsproblemer som er fokusert på strenger før intervjuene dine. I denne artikkelen lærer du hvordan du finner det hyppigst forekommende tegnet i en streng.

Eksempler for å forstå problemet

Eksempel 1: La den angitte strengen være "Makeuseof". Tegnet 'e' forekommer to ganger i den gitte strengen, og alle de andre tegnene forekommer bare en gang. Dermed har tegnet 'e' den høyeste frekvensen i den gitte strengen.

Eksempel 2: La den gitte strengen være "Hun ser ost". Tegnet 'e' forekommer 6 ganger i den gitte strengen, og alle de andre tegnene forekommer mindre enn 6 ganger. Dermed har tegnet 'e' den høyeste frekvensen i den gitte strengen.

Tilnærming for å finne den hyppigst forekommende karakteren i en streng

Hashingsteknikken er den mest effektive måten å finne tegnet med den høyeste frekvensen i en streng. I denne teknikken krysses strengen, og hvert tegn i strengen hasheres i en rekke ASCII-tegn.

La inngangsstrengen være "Makeuseof", hvert tegn i denne strengen blir hash som følger:

frekvens ['M'] = 1

frekvens ['a] = 1

frekvens ['k'] = 1

frekvens ['e'] = 2

frekvens ['u'] = 1

frekvens ['s'] = 1

frekvens ['o'] = 1

frekvens ['f'] = 1

Indeksen for maksimumsverdien i frekvensoppsettet returneres. Her 2 er den høyeste verdien, derfor returneres 'e'.

C ++ - program for å finne karakteren med den høyeste frekvensen

Nedenfor er C ++ - programmet for å finne tegnet med høyest frekvens i en streng:

I slekt: Hvordan telle forekomster av en gitt karakter i en streng

// C ++ program for å finne tegnet
// har den høyeste frekvensen i en streng
#inkludere 
#inkludere 
#define ASCII_SIZE 256
bruker navneområde std;
char maxFrequencyChar (streng str)
{
// Array for å lagre hyppigheten til hvert tegn
// Initialiserte frekvensen til hvert tegn som 0
int frekvens [ASCII_SIZE] = {0};
// Finne lengde på inngangsstrengen
int lenOfStr = str.length ();
// Initialiser variabelen maxFrequency
int maxFrequency = -1;
// Initialiser variabelen maxFrequencyChar
røye maxFrequencyChar;
// Traversering og vedlikehold av
// frekvens for hvert tegn
for (int i = 0; i {
frekvens [str [i]] ++;
hvis (maxFrequency {
maxFrequency = frekvens [str [i]];
maxFrequencyChar = str [i];
}
}
retur maxFrequencyChar;
}
// Sjåførkode
int main ()
{
string str1 = "Hvilken heks er hvilken?";
cout << "str1:" << str1 << endl;
cout << "Den høyeste frekvensen er:" << maxFrequencyChar (str1) << endl;
string str2 = "Han kastet tre straffekast";
cout << "str2:" << str2 << endl;
cout << "Den høyeste frekvensen er:" << maxFrequencyChar (str2) << endl;
string str3 = "Eddie redigerte den";
cout << "str3:" << str3 << endl;
cout << "Den høyeste frekvensen er:" << maxFrequencyChar (str3) << endl;
string str4 = "Makeuseof";
cout << "str4:" << str4 << endl;
cout << "Den høyeste frekvensen er:" << maxFrequencyChar (str4) << endl;
string str5 = "Hun ser ost";
cout << "str5:" << str5 << endl;
cout << "Den høyeste frekvensen er:" << maxFrequencyChar (str5) << endl;
}

Produksjon:

str1: Hvilken heks er hvilken?
Den høyeste frekvensen er: h
str2: Han kastet tre straffekast
Den høyeste frekvensen er: e
str3: Eddie redigerte den
Den høyeste frekvensen er: d
str4: Makeuseof
Den høyeste frekvensen er: e
str5: Hun ser ost
Den høyeste frekvensen er: e

Python-program for å finne karakteren med den høyeste frekvensen

Nedenfor er Python-programmet for å finne tegnet med høyest frekvens i en streng:

I slekt: Hvordan reversere en streng i C ++, Python og JavaScript

# Python-program for å finne karakteren
# har den høyeste frekvensen i en streng
ASCII_SIZE = 256
def maxFrequencyChar (str):
# Array for å lagre hyppigheten til hvert tegn
# Initialiserte frekvensen til hvert tegn som 0
frekvens = [0] * ASCII_SIZE
# Initialiser variabelen maxFrequency
maxFrequency = -1
# Initialiser variabelen maxFrequencyChar
maxFrequencyChar = ''
# Å krysse og vedlikeholde
# frekvens for hvert tegn
for jeg i str:
frekvens [ord (i)] + = 1
for jeg i str:
hvis maxFrequency maxFrequency = frekvens [ord (i)]
maxFrequencyChar = i
retur maxFrequencyChar
# Førerkode
str1 = "Hvilken heks er hvilken?"
skriv ut ("str1:", str1)
print ("Den høyeste frekvensen er:", maxFrequencyChar (str1))
str2 = "Han kastet tre straffekast"
skriv ut ("str2:", str2)
print ("Den høyeste frekvensen er:", maxFrequencyChar (str2))
str3 = "Eddie redigerte den"
skriv ut ("str3:", str3)
print ("Den høyeste frekvensen er:", maxFrequencyChar (str3))
str4 = "Makeuseof"
skriv ut ("str4:", str4)
print ("Den høyeste frekvensen er:", maxFrequencyChar (str4))
str5 = "Hun ser ost"
skriv ut ("str5:", str5)
print ("Den høyeste frekvensen er:", maxFrequencyChar (str5))

Produksjon:

str1: Hvilken heks er hvilken?
Den høyeste frekvensen er: h
str2: Han kastet tre straffekast
Den høyeste frekvensen er: e
str3: Eddie redigerte den
Den høyeste frekvensen er: d
str4: Makeuseof
Den høyeste frekvensen er: e
str5: Hun ser ost
Den høyeste frekvensen er: e

C Program for å finne karakteren med den høyeste frekvensen

Nedenfor er C-programmet for å finne tegnet med høyest frekvens i en streng:

I slekt: Hvordan finne vokaler, konsonanter, sifre og spesialtegn i en streng

// C-program for å finne karakteren
// har den høyeste frekvensen i en streng
#inkludere 
#inkludere 
#define ASCII_SIZE 256
bruker navneområde std;
char maxFrequencyChar (char * str)
{
// Array for å lagre hyppigheten til hvert tegn
// Initialiserte frekvensen til hvert tegn som 0
int frekvens [ASCII_SIZE] = {0};
// Finne lengde på inngangsstrengen
int lenOfStr = strlen (str);
// Initialiser variabelen maxFrequency
int maxFrequency = 0;
// Initialiser variabelen maxFrequencyChar
røye maxFrequencyChar;
// Traversering og vedlikehold av
// frekvens for hvert tegn
for (int i = 0; i {
frekvens [str [i]] ++;
hvis (maxFrequency {
maxFrequency = frekvens [str [i]];
maxFrequencyChar = str [i];
}
}
retur maxFrequencyChar;
}
// Sjåførkode
int main ()
{
char str1 [] = "Hvilken heks er hvilken?";
printf ("str1:% s", str1);
printf ("Det høyeste frekvensen er:% c \ ⁠n", maxFrequencyChar (str1));
char str2 [] = "Han kastet tre straffekast";
printf ("str2:% s", str2);
printf ("Den høyeste frekvensen er:% c \ ⁠n", maxFrequencyChar (str2));
char str3 [] = "Eddie redigerte den";
printf ("str3:% s", str3);
printf ("Den høyeste frekvensen er:% c \ ⁠n", maxFrequencyChar (str3));
char str4 [] = "Makeuseof";
printf ("str4:% s", str4);
printf ("Den høyeste frekvensen er:% c \ ⁠n", maxFrequencyChar (str4));
char str5 [] = "Hun ser ost";
printf ("str1:% s", str5);
printf ("Den høyeste frekvensen er:% c \ ⁠n", maxFrequencyChar (str5));
}

Produksjon:

str1: Hvilken heks er hvilken?
Den høyeste frekvensen er: h
str2: Han kastet tre straffekast
Den høyeste frekvensen er: e
str3: Eddie redigerte den
Den høyeste frekvensen er: d
str4: Makeuseof
Den høyeste frekvensen er: e
str5: Hun ser ost
Den høyeste frekvensen er: e

JavaScript-program for å finne karakteren med den høyeste frekvensen

Nedenfor er JavaScript-programmet for å finne tegnet med høyest frekvens i en streng:

// JavaScript-program for å finne tegnet
// har den høyeste frekvensen i en streng
la ASCII_SIZE = 256;
funksjon maxFrequencyChar (str)
{
// Array for å lagre hyppigheten til hvert tegn
// Initialiserte frekvensen til hvert tegn som 0
la frekvens = ny matrise (ASCII_SIZE);
for (la i = 0; i {
frekvens [i] = 0;
}
// Finne lengde på inngangsstrengen
la lenOfStr = str. lengde;
for (la i = 0; i {
frekvens [str [i] .charCodeAt (0)] + = 1;
}
// Initialiser variabelen maxFrequency
la maxFrequency = -1;
// Initialiser variabelen maxFrequencyChar
la maxFrequencyChar = '';
// Traversering og vedlikehold av
// frekvens for hvert tegn
for (la i = 0; i {
hvis (maxFrequency {
maxFrequency = frekvens [str [i] .charCodeAt (0)];
maxFrequencyChar = str [i];
}
}
retur maxFrequencyChar;
}
// Sjåførkode
let str1 = "Hvilken heks er hvilken?";
document.write ("str1:" + str1 + "
");
document.write ("Den høyeste frekvensen er:" + maxFrequencyChar (str1) + "
")
la str2 = "Han kastet tre straffekast";
document.write ("str2:" + str2 + "
");
document.write ("Den høyeste frekvensen er:" + maxFrequencyChar (str2) + "
")
let str3 = "Eddie redigerte det";
document.write ("str3:" + str3 + "
");
document.write ("Den høyeste frekvensen er:" + maxFrequencyChar (str3) + "
")
la str4 = "Makeuseof";
document.write ("str4:" + str4 + "
");
document.write ("Den høyeste frekvensen er:" + maxFrequencyChar (str4) + "
")
la str5 = "Hun ser ost";
document.write ("str5:" + str5 + "
");
document.write ("Den høyeste frekvensen er:" + maxFrequencyChar (str5) + "
")

Produksjon:

str1: Hvilken heks er hvilken?
Den høyeste frekvensen er: h
str2: Han kastet tre straffekast
Den høyeste frekvensen er: e
str3: Eddie redigerte den
Den høyeste frekvensen er: d
str4: Makeuseof
Den høyeste frekvensen er: e
str5: Hun ser ost
Den høyeste frekvensen er: e

Analyser tid og romkompleksitet

Tidskompleksiteten til maxFrequencyChar () funksjonen er På). Romkompleksiteten til maxFrequencyChar () funksjonen er O (1) som et fast mellomrom (Hash-array). Det avhenger ikke av størrelsen på inngangsstrengen.

Big-O-notasjon gir deg en måte å beregne hvor lang tid det vil ta å kjøre koden din. Det er et av de viktigste konseptene for analyse av algoritmer. Hvis du er programmerer, må du vite om Big-O Notation.

Yuvraj Chandra (30 artikler publisert)

Yuvraj er en informatikk-student ved University of Delhi, India. Han brenner for Full Stack Web Development. Når han ikke skriver, utforsker han dybden i forskjellige teknologier.

Mer fra Yuvraj Chandra