Print all the duplicates in the input string.

Mon, Feb 22, 2010

Write an efficient C program to print all the duplicates and their counts in the input string

Algorithm: Let input string be “geeksforgeeks”
1: Construct character count array from the input string.
count['e'] = 4
count['g'] = 2
count['k'] = 2
……
2: Print all the indexes from the constructed array which have value greater than 0.

Solution

# include <stdio.h>
# include <stdlib.h>
# define NO_OF_CHARS 256
 
/* Returns an array of size 256 containg count
   of characters in the passed char array */
int *getCharCountArray(char *str)
{
   int *count = (int *)calloc(sizeof(int), NO_OF_CHARS);
   int i;
 
   for (i = 0; *(str+i);  i++)
      count[*(str+i)]++;
 
   return count;
}
 
/* Print duplicates present in the passed string */
void printDups(char *str)
{
  int *count = getCharCountArray(str);
  int i;
  char temp;
 
  for (i = 0; i < NO_OF_CHARS; i++)
    if(count[i] > 1)
        printf("%c,  count = %d \n", i,  count[i]);
}
 
/* Driver program to test to pront printDups*/
int main()
{
    char str[] = "test string";
    printDups(str);
    getchar();
    return 0;
}

Time Complexity: O(n)
Space Complexity: We can say O(1) as array size is fixed and not dependent of length of the input string

Sharing ~ Helping Other:

Print all the duplicates in the input string.

Other Posts:

This post was written by:

Leave a Reply