Data Structures - Data Structure - character that repeats itself

GeekInterview.com > Interview Questions > Concepts > Data Structures

Go To First | Previous Question | Next Question

Data Structures | Question 182 of 193

Data Structure - character that repeats itself

Given a string of characters (let us say there are about 100 characters or more in the string), what is the most efficient method to use for finding out the character that repeats itself the most?Is it possible for us to use some kind of data structure for this?, if this is so,which is the best one that needs to be used?

Total Answers and Comments: 5

Last Update: April 03, 2008 Asked by: jobchicago

Sponsored Links

Best Rated Answer

—

No best answer available. Please pick the good answer available or submit your answer.

December 11, 2007 05:42:29

purnendu_patra

Member Since: December 2007 Contribution: 2

RE: Data Structure - character that repeats itself

Th solution I can think of is of complexity O(n) by using an additional array of size 26.

Scan the entire array and increase the counter for the respective characters. After the scan is done we need another scan of those counters to find the maximum one and that will be the chanracter with maximum frequency. this will also take O(n) time.

I am eager to a get solution better than this..:-)

Is this answer useful? Yes | No

February 08, 2008 02:32:51

Vishwas.p

Member Since: February 2008 Contribution: 4

RE: Data Structure - character that repeats itself

#include <string.h>
#include <unistd.h>
#include <stdio.h>
#include<stdlib.h>
main()
{
int i=0,l,big,ascii,counter[300],value;
char s[100];
for(i=0;i<300;i++) counter[i]=0;
printf("nEnter the string : ");
scanf("%s",&s);
printf("String = %s",s);
l=strlen(s);
printf("nlength = %dnn",l);
for(i=0;i<l;i++)
{
    ascii = s[i];
    final = ascii;
    counter[ascii]++;
}
big = counter[0];
for(i=0;i<300;i++)
{
   if (counter[i]>big)
    {
    big = counter[i];
    value = i;
    }
}

printf(" %c is max repeated letter for %d timesn",value,big);

}

Is this answer useful? Yes | No

February 19, 2008 03:26:01

contact.nidhigupta

Member Since: January 2008 Contribution: 3

RE: Data Structure - character that repeats itself

Key points are:
1) Max number of characters can only be 256.
2) There is need to specify only the character repeating max no. of times.

so i think one simple solution can be:

#include <stdio.h>

#include<stdlib.h>

#define MAXNUMCHAR 256
void main()

{

int i=0;

char s[100];

char ascii = 0;

int counter[MAXNUMCHAR] = {0};

char max = 0;

int maxNum = 0;printf(

"nEnter the string : ");

gets(s);

printf("String = %sn",s);for(i=0; s[i] != ''; i++)

{

ascii = s[i];

counter[ascii]++;

if (counter[ascii] > max) {

max = counter[ascii];

maxNum = ascii;

}

printf(" %c is max repeated letter for %d timesn", maxNum, max);

_getch();

}

Is this answer useful? Yes | No

February 23, 2008 22:08:12

Ashish.Shekhar

Member Since: February 2008 Contribution: 3

RE: Data Structure - character that repeats itself

I have an opinion that a hash table with indexing based on the ascii values of the characters would bring the complexity down further and would add some time benefits as well.

Is this answer useful? Yes | No

April 03, 2008 17:46:18

pvsola

Member Since: March 2008 Contribution: 6

RE: Data Structure - character that repeats itself

There is an way to solve this issue with complexity of O(n).

1. MAke an array size of 256

2. Using each charater read from the string as an index incremented the counter of corresponding character.

3. Let that counter be max, so inshort you have variables holding a char with number of times repeated in the string.

4. Repeat the proceess for all the characters and compare it with current max counter, if maximum change it

There might be posibility of more than one charater haivng same max counter, problem don't ask for such situation, any way for an interview keep it precise guys!!

Is this answer useful? Yes | No

Go To Top