Hur man hittar den mest förekommande karaktären i en sträng

Strängar är ett mycket viktigt ämne i programmeringsintervjuer. Det är klokt att träna på några programmeringsproblem med fokus på strängar innan dina intervjuer. I den här artikeln lär du dig hur du hittar det tecken som oftast förekommer i en sträng.

Exempel för att förstå problemet

Exempel 1: Låt den givna strängen vara "Makeuseof". Tecknet 'e' förekommer två gånger i den angivna strängen och alla andra tecken förekommer bara en gång. Således har tecknet 'e' den högsta frekvensen i den givna strängen.

Exempel 2: Låt den givna strängen vara "Hon ser ost". Tecknet 'e' förekommer 6 gånger i den angivna strängen och alla andra tecken förekommer mindre än 6 gånger. Således har tecknet 'e' den högsta frekvensen i den givna strängen.

Tillvägagångssätt för att hitta den mest förekommande karaktären i en sträng

Hashningstekniken är det mest effektiva sättet att hitta karaktären med den högsta frekvensen i en sträng. I den här tekniken passeras strängen och varje tecken i strängen hashades till en matris med ASCII-tecken.

Låt inmatningssträngen vara "Makeuseof", varje tecken i denna sträng hashades som följer:

frekvens ['M'] = 1

frekvens ['a] = 1

frekvens ['k'] = 1

frekvens ['e'] = 2

frekvens ['u'] = 1

frekvens ['s'] = 1

frekvens ['o'] = 1

frekvens ['f'] = 1

Indexet för det maximala värdet i frekvensuppsättningen returneras. Här 2 är det högsta värdet, därför returneras 'e'.

C ++ - program för att hitta karaktären med den högsta frekvensen

Nedan följer C ++ - programmet för att hitta karaktären med högst frekvens i en sträng:

Relaterad: Hur man räknar förekomsten av en given karaktär i en sträng

// C ++ - program för att hitta karaktären
// med den högsta frekvensen i en sträng
#omfatta 
#omfatta 
#define ASCII_SIZE 256
använder namnrymd std;
char maxFrequencyChar (strängstr)
{
// Array för att lagra frekvensen för varje tecken
// Initierade frekvensen för varje tecken som 0
int frekvens [ASCII_SIZE] = {0};
// Hitta längden på inmatningssträngen
int lenOfStr = str.length ();
// Initiera maxFrequency-variabeln
int maxFrequency = -1;
// Initiera maxFrequencyChar-variabeln
char maxFrequencyChar;
// Korsning och underhåll av
// frekvens för varje tecken
för (int i = 0; i {
frekvens [str [i]] ++;
om (maxFrequency {
maxFrequency = frekvens [str [i]];
maxFrequencyChar = str [i];
}
}
returnera maxFrequencyChar;
}
// Förarkod
int main ()
{
string str1 = "Vilken häxa är vilken?";
cout << "str1:" << str1 << endl;
cout << "Den högsta frekvensen är:" << maxFrequencyChar (str1) << endl;
string str2 = "Han kastade tre fria kast";
cout << "str2:" << str2 << endl;
cout << "Den högsta frekvensen är:" << maxFrequencyChar (str2) << endl;
string str3 = "Eddie redigerade det";
cout << "str3:" << str3 << endl;
cout << "Den högsta frekvensen är:" << maxFrequencyChar (str3) << endl;
string str4 = "Makeuseof";
cout << "str4:" << str4 << endl;
cout << "Den högsta frekvensen är:" << maxFrequencyChar (str4) << endl;
string str5 = "Hon ser ost";
cout << "str5:" << str5 << endl;
cout << "Den högsta frekvensen är:" << maxFrequencyChar (str5) << endl;
}

Produktion:

str1: Vilken häxa är vilken?
Den högsta frekvensen är: h
str2: Han kastade tre fria kast
Den högsta frekvensen är: e
str3: Eddie redigerade den
Den högsta frekvensen är: d
str4: Makeuseof
Den högsta frekvensen är: e
str5: Hon ser ost
Den högsta frekvensen är: e

Python-programmet för att hitta karaktären med den högsta frekvensen

Nedan följer Python-programmet för att hitta karaktären med den högsta frekvensen i en sträng:

Relaterad: Hur man gör om en sträng i C ++, Python och JavaScript

# Python-program för att hitta karaktären
# har den högsta frekvensen i en sträng
ASCII_SIZE = 256
def maxFrequencyChar (str):
# Array för att lagra frekvensen för varje tecken
# Initierade frekvensen för varje tecken som 0
frekvens = [0] * ASCII_SIZE
# Initiera maxFrequency-variabeln
maxFrequency = -1
# Initiera maxFrequencyChar-variabeln
maxFrequencyChar = ''
# Korsning och underhåll av
# frekvens för varje tecken
för jag i str:
frekvens [ord (i)] + = 1
för jag i str:
om maxFrequency maxFrequency = frekvens [ord (i)]
maxFrequencyChar = i
returnera maxFrequencyChar
# Förarkod
str1 = "Vilken häxa är vilken?"
skriva ut ("str1:", str1)
print ("Den högsta frekvensen är:", maxFrequencyChar (str1))
str2 = "Han kastade tre fria kast"
skriva ut ("str2:", str2)
print ("Den högsta frekvensen är:", maxFrequencyChar (str2))
str3 = "Eddie redigerade det"
skriva ut ("str3:", str3)
print ("Den högsta frekvensen är:", maxFrequencyChar (str3))
str4 = "Makeuseof"
skriva ut ("str4:", str4)
print ("Den högsta frekvensen är:", maxFrequencyChar (str4))
str5 = "Hon ser ost"
skriva ut ("str5:", str5)
print ("Den högsta frekvensen är:", maxFrequencyChar (str5))

Produktion:

str1: Vilken häxa är vilken?
Den högsta frekvensen är: h
str2: Han kastade tre fria kast
Den högsta frekvensen är: e
str3: Eddie redigerade den
Den högsta frekvensen är: d
str4: Makeuseof
Den högsta frekvensen är: e
str5: Hon ser ost
Den högsta frekvensen är: e

C Program för att hitta karaktären med den högsta frekvensen

Nedan finns C-programmet för att hitta karaktären med högst frekvens i en sträng:

Relaterad: Hur man hittar vokaler, konsonanter, siffror och specialtecken i en sträng

// C-program för att hitta karaktären
// med den högsta frekvensen i en sträng
#omfatta 
#omfatta 
#define ASCII_SIZE 256
använder namnrymd std;
char maxFrequencyChar (char * str)
{
// Array för att lagra frekvensen för varje tecken
// Initierade frekvensen för varje tecken som 0
int frekvens [ASCII_SIZE] = {0};
// Hitta längden på inmatningssträngen
int lenOfStr = strlen (str);
// Initiera maxFrequency-variabeln
int maxFrequency = 0;
// Initiera maxFrequencyChar-variabeln
char maxFrequencyChar;
// Korsning och underhåll av
// frekvens för varje tecken
för (int i = 0; i {
frekvens [str [i]] ++;
om (maxFrequency {
maxFrequency = frekvens [str [i]];
maxFrequencyChar = str [i];
}
}
returnera maxFrequencyChar;
}
// Förarkod
int main ()
{
char str1 [] = "Vilken häxa är vilken?";
printf ("str1:% s", str1);
printf ("Den högsta frekvensen är:% c \ ⁠n", maxFrequencyChar (str1));
char str2 [] = "Han kastade tre fria kast";
printf ("str2:% s", str2);
printf ("Den högsta frekvensen är:% c \ ⁠n", maxFrequencyChar (str2));
char str3 [] = "Eddie redigerade det";
printf ("str3:% s", str3);
printf ("Den högsta frekvensen är:% c \ ⁠n", maxFrequencyChar (str3));
char str4 [] = "Makeuseof";
printf ("str4:% s", str4);
printf ("Den högsta frekvensen är:% c \ ⁠n", maxFrequencyChar (str4));
char str5 [] = "Hon ser ost";
printf ("str1:% s", str5);
printf ("Den högsta frekvensen är:% c \ ⁠n", maxFrequencyChar (str5));
}

Produktion:

str1: Vilken häxa är vilken?
Den högsta frekvensen är: h
str2: Han kastade tre fria kast
Den högsta frekvensen är: e
str3: Eddie redigerade den
Den högsta frekvensen är: d
str4: Makeuseof
Den högsta frekvensen är: e
str5: Hon ser ost
Den högsta frekvensen är: e

JavaScript-program för att hitta karaktären med den högsta frekvensen

Nedan följer JavaScript-programmet för att hitta karaktären med den högsta frekvensen i en sträng:

// JavaScript-program för att hitta karaktären
// med den högsta frekvensen i en sträng
låt ASCII_SIZE = 256;
funktion maxFrequencyChar (str)
{
// Array för att lagra frekvensen för varje tecken
// Initierade frekvensen för varje tecken som 0
låt frekvens = ny matris (ASCII_SIZE);
för (låt i = 0; i {
frekvens [i] = 0;
}
// Hitta längden på inmatningssträngen
låt lenOfStr = str. längd;
för (låt i = 0; i {
frekvens [str [i] .charCodeAt (0)] + = 1;
}
// Initiera maxFrequency-variabeln
låt maxFrequency = -1;
// Initiera maxFrequencyChar-variabeln
låt maxFrequencyChar = '';
// Korsning och underhåll av
// frekvens för varje tecken
för (låt i = 0; i {
om (maxFrequency {
maxFrequency = frekvens [str [i] .charCodeAt (0)];
maxFrequencyChar = str [i];
}
}
returnera maxFrequencyChar;
}
// Förarkod
let str1 = "Vilken häxa är vilken?";
document.write ("str1:" + str1 + "
");
document.write ("Den högsta frekvensen är:" + maxFrequencyChar (str1) + "
")
let str2 = "Han kastade tre fria kast";
document.write ("str2:" + str2 + "
");
document.write ("Den högsta frekvensen är:" + maxFrequencyChar (str2) + "
")
let str3 = "Eddie redigerade det";
document.write ("str3:" + str3 + "
");
document.write ("Den högsta frekvensen är:" + maxFrequencyChar (str3) + "
")
let str4 = "Makeuseof";
document.write ("str4:" + str4 + "
");
document.write ("Den högsta frekvensen är:" + maxFrequencyChar (str4) + "
")
let str5 = "Hon ser ost";
document.write ("str5:" + str5 + "
");
document.write ("Den högsta frekvensen är:" + maxFrequencyChar (str5) + "
")

Produktion:

str1: Vilken häxa är vilken?
Den högsta frekvensen är: h
str2: Han kastade tre fria kast
Den högsta frekvensen är: e
str3: Eddie redigerade den
Den högsta frekvensen är: d
str4: Makeuseof
Den högsta frekvensen är: e
str5: Hon ser ost
Den högsta frekvensen är: e

Analysera tid och rymdkomplexitet

Tidskomplexiteten hos maxFrequencyChar () funktionen är På). Utrymmets komplexitet maxFrequencyChar () funktionen är O (1) som ett fast utrymme (Hash-array). Det beror inte på ingångssträngens storlek.

Big-O-notering ger dig ett sätt att beräkna hur lång tid det tar att köra din kod. Det är ett av de viktigaste begreppen för analys av algoritmer. Om du är programmerare måste du veta om Big-O Notation.

Yuvraj Chandra (30 artiklar publicerade)

Yuvraj är studenter vid datavetenskap vid University of Delhi, Indien. Han brinner för Full Stack webbutveckling. När han inte skriver utforskar han djupet i olika tekniker.

Mer från Yuvraj Chandra