String: Program to find duplicate chars in a string

Write a program to find duplicate chars in a String

Example

String sentence = "This string contains Repeated Chars!";

Repeated Characters are:   a e h i n r s t

Approach

• Iterate over the string and store the count the occurrences of each character using a hashmap
• If the count is greater than 1 then we store it in an array and display it
• Or we can iterate over hashmap and for all characters whose count is > 1, we can print it

Algorithm

1. Create a key-value pair hashmap named charCount to store the count of each character
2. Iterate through the string character by character:
3. Check if the character is present in the map:
   • If present: Increment value of charCount for the character by one
   • If not present: Add an entry to charCount and assign the value equal to 1
4. Create an array repeatedChars to store the repeated characters
5. Iterate through the charCount hashmap:
6. If the current char count > 1 then push the current char in array repeatedChars
7. Return repeatedChars

Complexity

Time Complexity: O(N)
Space Complexity: O(N)

The Time Complexity of the algorithm is linear as we are just iterating through the string
The Space Complexity is also linear because in the worst case all the chars will be different
and we have to store all of them in the hashmap.

Java Code

import java.util.ArrayList;
import java.util.HashMap;
import java.util.Map;
     
class StringOperations {

     public static ArrayList getCharsRepeated(String givenString) {
       
        // Iterate through the string and find count of each characters
       Map charCount = new HashMap();
       
       for (int index = 0; index < givenString.length(); index++) {
         Character currentChar = givenString.charAt(index);
         if (charCount.containsKey(currentChar)) {
           charCount.put(currentChar, charCount.get(currentChar) + 1);
         } else {
           charCount.put(currentChar, 1);
         }
       }
     
       // Iterating through the map and finding the characters have count greater than 1
       ArrayList repeatedChars = new ArrayList();
       
        for (Map.Entry charEntry : charCount.entrySet()) {
         if (charEntry.getValue() > 1) {
           repeatedChars.add(charEntry.getKey());
         }
       }
       
       return repeatedChars;
     }
     
     public static void main(String[] args) {
       String givenString = "This string contains Repeated Chars!";
       ArrayList charsRepeated = getCharsRepeated(givenString);
     
       System.out.print("Input String: " + givenString);
     
       // Printing the result
       System.out.print("Repeated Characters are: ");
       for (int index = 0; index < charsRepeated.size(); index++) {
         System.out.print(charsRepeated.get(index) + " ");
       }
     }
 }

Output

Input String: This string contains Repeated Chars!
Repeated Characters are:   a e h i n r s t

Note: Space(' ') is the first character in the output above