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