CareerCup

Use an integer array of size 255. For each character occurrence increase the corresponding count and compare the new count to current global maximum.

Hi, This is the efficient code in C++ for finding out first most populas character.

char findFirstMostPopulas (char *strPtr)
{
int freq[256] = { 0 };
char *charPtr = strPtr;

while ( *charPtr != '\0')
{
freq[*charPtr]++;
charPtr++;
}
charPtr = strPtr;
char* mostPopulas = charPtr;
while ( *charPtr != '\0' )
{
if (freq[*mostPopulas] < freq[*charPtr])
mostPopulas = charPtr;
charPtr++;
}

return *mostPopulas;
}

hash the charactes

hash the characters

By populous do you mean the one that repeats the most in a string?

use segment trees

Hash Table is the best option ... iterate once over the character of the string, and have a counter to fetch the previous value and increment and insert it again.

//The second solution like Integer arr[255] would fail in case of other characters like åß∂ƒ©˙∆˚¬Ω≈ç∫˜¡™£¢∞¶•ªº

#include <stdio.h>

#define N 256

int findMostPopChar(char *s){
int ht[N];
int maxCnt = 0;
int maxInd = -1;
int i;

for(i = 0 ; i < N; i++){
ht[i] = 0;
}

while(*s++){
/* assert to make sure *s is in [0,255] range */
ht[*s]++;

if(ht[*s] > maxCnt){
maxCnt = ht[*s];
maxInd = *s;
}
}
return maxInd;
}

int main(){

char *s = "abjdjdjdjakjdkdjdkjdjdjdjdjkdjkd ";
printf("most pop. char = %c\n", findMostPopChar(s));
return 0;
}

string str("abcdeabcdefghikjaa");

int len = str.length();

int location, maxcount;
char ch;
int noftimes;

location = maxcount = noftimes = 0;
for (int i = 0 ; i < len ; i++)
{
ch = str[i];
noftimes = 0;
for(int j = i+1; j< len ; j++)
{
if(ch == str[j])
{
noftimes++;
}
}

if (noftimes > maxcount )
{
maxcount = noftimes;
location = i;
}
}

return str[location];
}


complexity is o(n2);