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 1.
Solution
C++
// C++ program to count all duplicates // from string using hashing # include <iostream> using namespace std; # define NO_OF_CHARS 256 class gfg { public : /* Fills count array with frequency of characters */ void fillCharCounts( char *str, int *count) { int i; for (i = 0; *(str + i); i++) count[*(str + i)]++; } /* Print duplicates present in the passed string */ void printDups( char *str) { // Create an array of size 256 and fill // count of every character in it int *count = ( int *) calloc (NO_OF_CHARS, sizeof ( int )); fillCharCounts(str, count); // Print characters having count more than 0 int i; for (i = 0; i < NO_OF_CHARS; i++) if (count[i] > 1) printf ( "%c, count = %d
" , i, count[i]); free (count); } }; /* Driver code*/ int main() { gfg g ; char str[] = "test string" ; g.printDups(str); //getchar(); return 0; } // This code is contributed by SoM15242 |
C
// C program to count all duplicates from string using hashing # include <stdio.h> # include <stdlib.h> # define NO_OF_CHARS 256 /* Fills count array with frequency of characters */ void fillCharCounts( char *str, int *count) { int i; for (i = 0; *(str+i); i++) count[*(str+i)]++; } /* Print duplicates present in the passed string */ void printDups( char *str) { // Create an array of size 256 and fill count of every character in it int *count = ( int *) calloc (NO_OF_CHARS, sizeof ( int )); fillCharCounts(str, count); // Print characters having count more than 0 int i; for (i = 0; i < NO_OF_CHARS; i++) if (count[i] > 1) printf ( "%c, count = %d
" , i, count[i]); free (count); } /* Driver program to test to pront printDups*/ int main() { char str[] = "test string" ; printDups(str); getchar (); return 0; } |
Java
// Java program to count all duplicates from string using hashing public class GFG { static final int NO_OF_CHARS = 256 ; /* Fills count array with frequency of characters */ static void fillCharCounts(String str, int [] count) { for ( int i = 0 ; i < str.length(); i++) count[str.charAt(i)]++; } /* Print duplicates present in the passed string */ static void printDups(String str) { // Create an array of size 256 and fill count of every character in it int count[] = new int [NO_OF_CHARS]; fillCharCounts(str, count); for ( int i = 0 ; i < NO_OF_CHARS; i++) if (count[i] > 1 ) System.out.printf( "%c, count = %d
" , i, count[i]); } // Driver Method public static void main(String[] args) { String str = "test string" ; printDups(str); } } |
Python
# Python program to count all duplicates from string using hashing NO_OF_CHARS = 256 # Fills count array with frequency of characters def fillCharCounts(string, count): for i in string: count[ ord (i)] + = 1 return count # Print duplicates present in the passed string def printDups(string): # Create an array of size 256 and fill count of every character in it count = [ 0 ] * NO_OF_CHARS count = fillCharCounts(string,count) # Utility Variable k = 0 # Print characters having count more than 0 for i in count: if int (i) > 1 : print chr (k) + ", count = " + str (i) k + = 1 # Driver program to test the above function string = "test string" print printDups(string) # This code is contributed by Bhavya Jain |
C#
// C# program to count all duplicates // from string using hashing using System; class GFG { static int NO_OF_CHARS = 256; /* Fills count array with frequency of characters */ static void fillCharCounts(String str, int [] count) { for ( int i = 0; i < str.Length; i++) count[str[i]]++; } /* Print duplicates present in the passed string */ static void printDups(String str) { // Create an array of size 256 and // fill count of every character in it int []count = new int [NO_OF_CHARS]; fillCharCounts(str, count); for ( int i = 0; i < NO_OF_CHARS; i++) if (count[i] > 1) Console.WriteLine(( char )i + ", " + "count = " + count[i]); } // Driver Method public static void Main() { String str = "test string" ; printDups(str); } } // This code is contributed by Sam007 |
PHP
<?php // PHP program to count // all duplicates from // string using hashing function fillCharCounts( $str , $count ) { for ( $i = 0; $i < strlen ( $str ); $i ++) $count [ord( $str [ $i ])]++; for ( $i = 0; $i < 256; $i ++) if ( $count [ $i ] > 1) echo chr ( $i ) . ", " . "count = " . ( $count [ $i ]) . "
" ; } // Print duplicates present // in the passed string function printDups( $str ) { // Create an array of size // 256 and fill count of // every character in it $count = array (); for ( $i = 0; $i < 256; $i ++) $count [ $i ] = 0; fillCharCounts( $str , $count ); } // Driver Code $str = "test string" ; printDups( $str ); // This code is contributed by Sam007 ?> |
Output :
s, count = 2 t, count = 3
Time Complexity : O(n)
Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.
leave a comment
0 Comments