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 202

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: 6

Last Update: October 23, 2009 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

October 23, 2009 01:23:23

vinod148

Member Since: April 2008 Contribution: 6

RE: Data Structure - character that repeats itself

There is no way for less that O(n) solution as we have to traverse the string atleast once.

By traversing only once we can find the solution

Keep another variable which tracks the current highest occured character.

Is this answer useful? Yes | No

Go To Top

User Name		Remember Me?
Password

Question Bank