Find Duplicate Characters in a String in Java

One of the common interview questions asked at MAANG companies is how to find duplicate characters in a string. In this post, we will walk through various approaches, from basic to optimized, to tackle this problem.

Problem Statement

Given a string, find all the duplicate characters and their frequencies.

Input

• A single string str (e.g., "programming").

Output

• A list of characters that appear more than once, along with their frequency.

For example, given the input "programming", the output should be:

r: 2
g: 2
m: 2

Possible Solutions

1. Using a HashMap

The most common and efficient approach is to use a HashMap to store the frequency of each character. We loop through the string, count each character’s occurrences, and then check for duplicates.

import java.util.HashMap;
import java.util.Map;

public class DuplicateCharacters {
    public static void main(String[] args) {
        String input = "programming";
        findDuplicateCharacters(input);
    }

    public static void findDuplicateCharacters(String str) {
        Map<Character, Integer> charCountMap = new HashMap<>();

        for (char c : str.toCharArray()) {
            charCountMap.put(c, charCountMap.getOrDefault(c, 0) + 1);
        }

        System.out.println("Duplicate characters:");
        for (Map.Entry<Character, Integer> entry : charCountMap.entrySet()) {
            if (entry.getValue() > 1) {
                System.out.println(entry.getKey() + ": " + entry.getValue());
            }
        }
    }
}

Step-by-Step Explanation:

1. Create a HashMap to store the frequency of each character.
2. Iterate through the string and update the map for each character.
3. Check and print characters that have a frequency greater than 1.

Time Complexity: O(n)
Space Complexity: O(k) (k is the number of unique characters)

2. Using Two Loops (Brute Force)

This approach is not the most efficient but demonstrates how you could solve the problem using two nested loops. We compare every character with every other character in the string.

public class DuplicateCharactersBruteForce {
    public static void main(String[] args) {
        String input = "programming";
        findDuplicateCharacters(input);
    }

    public static void findDuplicateCharacters(String str) {
        int n = str.length();
        System.out.println("Duplicate characters:");
        for (int i = 0; i < n; i++) {
            int count = 1;
            if (str.charAt(i) != '0') {
                for (int j = i + 1; j < n; j++) {
                    if (str.charAt(i) == str.charAt(j)) {
                        count++;
                        str = str.substring(0, j) + '0' + str.substring(j + 1);
                    }
                }
                if (count > 1) {
                    System.out.println(str.charAt(i) + ": " + count);
                }
            }
        }
    }
}

Explanation:

• Use two loops to compare every character with every other character.
• If a duplicate is found, count it and replace the character in the string with ‘0’ to avoid counting it again.

Time Complexity: O(n^2)
Space Complexity: O(1)

This approach is not efficient for large strings and should be avoided in interview settings.

3. Using Sorting

If the string is sorted, finding duplicates becomes much easier as duplicates will appear consecutively. We can use the Arrays.sort() function.

import java.util.Arrays;

public class DuplicateCharactersSorting {
    public static void main(String[] args) {
        String input = "programming";
        findDuplicateCharacters(input);
    }

    public static void findDuplicateCharacters(String str) {
        char[] charArray = str.toCharArray();
        Arrays.sort(charArray);

        System.out.println("Duplicate characters:");
        int count = 1;
        for (int i = 1; i < charArray.length; i++) {
            if (charArray[i] == charArray[i - 1]) {
                count++;
            } else {
                if (count > 1) {
                    System.out.println(charArray[i - 1] + ": " + count);
                }
                count = 1;
            }
        }

        if (count > 1) {
            System.out.println(charArray[charArray.length - 1] + ": " + count);
        }
    }
}

Explanation:

1. Convert the string to a character array.
2. Sort the array.
3. Iterate through the array, checking for consecutive duplicate characters.

Time Complexity: O(n log n) due to sorting
Space Complexity: O(n) for storing the sorted array.

4. Using Frequency Array (For only Lowercase Alphabets)

If the input string only contains lowercase English letters (a-z), we can use an array of size 26 to store the frequency of each character.

public class DuplicateCharactersFrequencyArray {
    public static void main(String[] args) {
        String input = "programming";
        findDuplicateCharacters(input);
    }

    public static void findDuplicateCharacters(String str) {
        int[] frequency = new int[26]; // Only for lowercase a-z

        for (char c : str.toCharArray()) {
            frequency[c - 'a']++;
        }

        System.out.println("Duplicate characters:");
        for (int i = 0; i < 26; i++) {
            if (frequency[i] > 1) {
                System.out.println((char) (i + 'a') + ": " + frequency[i]);
            }
        }
    }
}

Explanation:

• Use an array of size 26 to store the frequency of each character.
• Iterate through the string and update the frequency array.
• Print characters with a frequency greater than 1.

Time Complexity: O(n)
Space Complexity: O(1) (since the array size is fixed at 26)

This approach is efficient but limited to lowercase letters.

Conclusion

There are multiple ways to solve the problem of finding duplicate characters in a string, each with its own trade-offs:

1. HashMap Approach: Efficient and flexible for any string.
2. Brute Force Approach: Simple but inefficient.
3. Sorting Approach: Useful but involves extra time for sorting.
4. Frequency Array Approach: Fastest but limited to lowercase letters.

Career Guidance

If you’re preparing for technical interviews, mastering problems like these will help you stand out. For those looking for career opportunities or guidance, feel free to submit your resume to Divi Tech Careers at Divi Tech Careers. For personalized career advice, you can also reach out to Divi Tech HR Solution (info@divisolutions.in).

Which approach do you prefer for finding duplicates? Let us know in the comments below, and don’t forget to like and share if you found this post helpful!