Given a string S, the task is to print all the duplicate characters with their occurrences in the given string.
Example:
Input: S = “neveropen”
Output:e, count = 4
g, count = 2
k, count = 2
s, count = 2Explanation: e,g,k,and s are characters which are occured in string in more than one times.
Find the duplicate characters in a string using Hashing.
- Store the characters count of a string in an unordered map which allows operations in constant time.
- Then, print the characters which have a frequency greater than 1.
Steps to implement the above approach:
- Declare a unordered map of the char-int pair.
- Traverse the string using a loop and increase the count of the present char in the map.
- Iterate through the map and print a character that has a value greater than one in map.
Below is the implementation of the above approach:
C++
// C++ program to count all duplicates// from string using maps#include <bits/stdc++.h>using namespace std;void printDups(string str){ unordered_map<char, int> count; for (int i = 0; i < str.length(); i++) { // increase the count of character str[i] by 1 count[str[i]]++; } // iterating through the unordered map for (auto it : count) { // if the count of characters is greater than 1 then // duplicate found if (it.second > 1) cout << it.first << ", count = " << it.second << "\n"; }}/* Driver code*/int main(){ string str = "test string"; printDups(str); return 0;} |
Java
/*package whatever //do not write package name here */import java.io.*;import java.util.*;class GFG { // Java program to count all duplicates // from string using maps static void printDups(String str) { Map<Character, Integer> count = new HashMap<>(); for (int i = 0; i < str.length(); i++) { if(count.containsKey(str.charAt(i))) count.put(str.charAt(i) , count.get(str.charAt(i))+1); else count.put(str.charAt(i),1); //increase the count of characters by 1 } for (Map.Entry<Character,Integer> mapElement : count.entrySet()) { //iterating through the unordered map if (mapElement.getValue() > 1) //if the count of characters is greater than 1 then duplicate found System.out.println(mapElement.getKey() + ", count = " + mapElement.getValue()); } } /* Driver program to test above function*/ public static void main(String args[]) { String str = "test string"; printDups(str); }}// This code is contributed by shinjanpatra |
Python3
# Python3 program to count all duplicates# from string using mapsdef printDups(Str): count = {} for i in range(len(Str)): if(Str[i] in count): count[Str[i]] += 1 else: count[Str[i]] = 1 #increase the count of characters by 1 for it,it2 in count.items(): #iterating through the unordered map if (it2 > 1): #if the count of characters is greater than 1 then duplicate found print(str(it) + ", count = "+str(it2)) # Driver codeStr = "test string"printDups(Str)# This code is contributed by shinjanpatra |
C#
// C# program to count all duplicates// from string using mapsusing System;using System.Collections.Generic;class GFG { static void printDups(String str) { SortedDictionary<char, int> count = new SortedDictionary<char , int>(); for (int i = 0; i < str.Length; i++) { if(count.ContainsKey(str[i])) { int temp = count[str[i]]; count.Remove(str[i]); count.Add(str[i] , temp + 1); } else count.Add(str[i],1); //increase the count of characters by 1 } foreach(KeyValuePair<char,int> mapElement in count) { //iterating through the SortedDIctionary if (mapElement.Value > 1) //if the count of characters is greater than 1 then duplicate found Console.WriteLine(mapElement.Key + ", count = " + mapElement.Value); } } /* Driver program to test above function*/ public static void Main(String[] args) { String str = "test string"; printDups(str); }}// This code is contributed by Abhijeet Kumar(abhijeet19403) |
Javascript
<script>// JavaScript program to count all duplicates// from string using mapsfunction printDups(str){ let count = new Map(); for (let i = 0; i < str.length; i++) { if(count.has(str[i])){ count.set(str[i],count.get(str[i])+1); } else{ count.set(str[i],1); } //increase the count of characters by 1 } for (let [it,it2] of count) { //iterating through the unordered map if (it2 > 1) //if the count of characters is greater than 1 then duplicate found document.write(it,", count = ",it2,"</br>"); }}/* Driver code*/let str = "test string";printDups(str); // This code is contributed by shinjanpatra</script> |
Output
t, count = 3 s, count = 2
Time Complexity: O(N), where N = length of the string passed and it takes O(1) time to insert and access any element in an unordered map
Auxiliary Space: O(K), where K = size of the map (0<=K<=input_string_length), in worst case space will be O(N).
Find the duplicate characters in a string using Sorting
If we sort the string then all duplicates will come together in the string. Then, traverse the string from starting index to the ending index and check if the neighbor character is same then increment the count by 1.
Steps to implement the above approach:
- Sort the given string.
- Loop through the sorted string to find the duplicates.
- If the next character is the same as the current character then we keep on counting the occurrence of that char.
- If the count is greater than one then we print the character and its count.
Below is the implementation for this approach:
C++
// C++ code to implement the above approach#include <algorithm>#include <iostream>#include <string>using namespace std;void printDuplicates(string str){ int len = str.length(); // Sorting the string sort(str.begin(), str.end()); // Loop through the sorted string to find duplicates for (int i = 0; i < len; i++) { int count = 1; // Counting the occurrences of each character while (i < len - 1 && str[i] == str[i + 1]) { count++; i++; } // Printing the duplicate character and its count if (count > 1) { cout << str[i] << ", count = " << count << endl; } }}int main(){ string str = "test string"; printDuplicates(str); return 0;}// This code is contributed by Veerendra_Singh_Rajpoot |
Java
// Java code to implement the above approachimport java.util.*;public class Main { public static void printDuplicates(String str) { int len = str.length(); // Sorting the string char[] chars = str.toCharArray(); Arrays.sort(chars); String sortedStr = new String(chars); // Loop through the sorted string to find duplicates for (int i = 0; i < len; i++) { int count = 1; // Counting the occurrences of each character while (i < len - 1 && sortedStr.charAt(i) == sortedStr.charAt(i + 1)) { count++; i++; } // Printing the duplicate character and its // count if (count > 1) { System.out.println(sortedStr.charAt(i) + ", count = " + count); } } } public static void main(String[] args) { String str = "test string"; printDuplicates(str); }}// This code is contributed by rutikbhosale |
Python3
def printDuplicates(str): # Converting string to list of characters char_list = list(str) # Sorting the list of characters char_list.sort() # Loop through the sorted list to find duplicates i = 0 while i < len(char_list): count = 1 # Counting the occurrences of each character while i < len(char_list)-1 and char_list[i] == char_list[i+1]: count += 1 i += 1 # Printing the duplicate character and its count if count > 1: print(char_list[i], ", count = ", count) i += 1str = "test string"printDuplicates(str) |
C#
using System;using System.Linq;class MainClass { public static void PrintDuplicates(string str) { int len = str.Length; // Sorting the string char[] chars = str.ToCharArray(); Array.Sort(chars); string sortedStr = new string(chars); // Loop through the sorted string to find duplicates for (int i = 0; i < len; i++) { int count = 1; // Counting the occurrences of each character while (i < len - 1 && sortedStr[i] == sortedStr[i + 1]) { count++; i++; } // Printing the duplicate character and its count if (count > 1) { Console.WriteLine(sortedStr[i] + ", count = " + count); } } } public static void Main (string[] args) { string str = "test string"; PrintDuplicates(str); }} |
Javascript
function printDuplicates(str) { let len = str.length; // Sorting the string str = str.split('').sort().join(''); // Loop through the sorted string to find duplicates for(let i = 0; i < len; i++) { let count = 1; // Counting the occurrences of each character while(i < len-1 && str[i] == str[i+1]) { count++; i++; } // Printing the duplicate character and its count if(count > 1) { console.log(str[i] + ", count = " + count); } }}let str = "test string";printDuplicates(str); |
Output
s, count = 2 t, count = 3
Time Complexity: O(N*logN), where n is the length of the string
Auxiliary Space: O(1), if you observe we did not use any extra space.
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
