StringProblem 3 of 43
Find Duplicate characters in a string
Problem Statement
Given a string, find all duplicate characters and their frequencies. A duplicate character is one that appears more than once in the string.
Example:
-
Input:
"programming" -
Output:
{r: 2, g: 2, m: 2}(characters appearing more than once) -
Input:
"hello" -
Output:
{l: 2}
Approach 1: Brute Force (Nested Loops)
Intuition
For each character, count its occurrences by traversing the entire string. Mark characters as visited to avoid counting duplicates.
Algorithm
- For each character in the string
- Count its occurrences in the entire string
- If count > 1 and not already processed, add to result
- Mark the character as processed
java
import java.util.*;
public class Solution {
public void findDuplicates(String s) {
int n = s.length();
boolean[] visited = new boolean[n];
for (int i = 0; i < n; i++) {
if (visited[i]) continue;
int count = 1;
for (int j = i + 1; j < n; j++) {
if (s.charAt(i) == s.charAt(j)) {
count++;
visited[j] = true;
}
}
if (count > 1) {
System.out.println(s.charAt(i) + " : " + count);
}
}
}
}Complexity Analysis
- Time Complexity: O(n²) - Nested loops for each character
- Space Complexity: O(n) - Visited array (can be O(1) if we modify string)
Approach 2: Optimal (Using HashMap/Frequency Array)
Intuition
Use a hash map or frequency array to count occurrences of each character in a single pass. Then iterate through the map to find characters with count > 1.
Algorithm
- Create a frequency map/array
- Traverse the string and count each character
- Iterate through the map and print characters with count > 1
java
import java.util.*;
public class Solution {
public void findDuplicates(String s) {
Map<Character, Integer> freq = new HashMap<>();
// Count frequency of each character
for (char c : s.toCharArray()) {
freq.put(c, freq.getOrDefault(c, 0) + 1);
}
// Print duplicates
System.out.println("Duplicate characters:");
for (Map.Entry<Character, Integer> entry : freq.entrySet()) {
if (entry.getValue() > 1) {
System.out.println(entry.getKey() + " : " + entry.getValue());
}
}
}
// Using array for ASCII characters
public void findDuplicatesArray(String s) {
int[] freq = new int[256]; // For all ASCII characters
for (char c : s.toCharArray()) {
freq[c]++;
}
System.out.println("Duplicate characters:");
for (int i = 0; i < 256; i++) {
if (freq[i] > 1) {
System.out.println((char) i + " : " + freq[i]);
}
}
}
}Complexity Analysis
- Time Complexity: O(n) - Single pass to count, O(k) to find duplicates where k is unique characters
- Space Complexity: O(k) - Space for frequency map, where k is number of unique characters (at most 256 for ASCII)
Approach 3: Using Sorting
Intuition
Sort the string first, then duplicate characters will be adjacent. Traverse once to find consecutive duplicates.
java
import java.util.*;
public class Solution {
public void findDuplicatesSorting(String s) {
char[] chars = s.toCharArray();
Arrays.sort(chars);
int n = chars.length;
int i = 0;
while (i < n) {
int count = 1;
while (i + count < n && chars[i] == chars[i + count]) {
count++;
}
if (count > 1) {
System.out.println(chars[i] + " : " + count);
}
i += count;
}
}
}Complexity Analysis
- Time Complexity: O(n log n) - Due to sorting
- Space Complexity: O(n) or O(1) - Depending on sorting algorithm and mutability
Key Takeaways
- HashMap/Frequency array is the most efficient approach for counting duplicates
- Using an array of size 26 (for lowercase) or 256 (for ASCII) provides O(1) access
- The sorting approach is useful when you need to modify the original string anyway
- Consider case sensitivity - convert to lowercase if needed
- This pattern (frequency counting) is fundamental for many string problems