Find All Duplicate Characters in a String - Java

@Note: This is categorized as “Difficult” because it tests whether the candidate knows how to avoid multiple-insertion bugs and how to choose an order-preserving Map implementation.

---

Category: Difficult | Concepts used: Frequency map, filtering, order preservation

---

Problem Statement

Given a string, list all the distinct characters that appear more than once (this is the natural follow-up to Q49 — instead of just counting, actually list them out).

Input : "programming"      Output: [r, g, m]

Examples (with edge scenarios)

#	Input	Output	Why
1	"programming"	[r, g, m]	These 3 characters each appear more than once
2	"" (empty)	[]	No characters at all
3	"abcdef" (no repeats)	[]	Every character appears exactly once
4	"aabbcc"	[a, b, c]	All three characters repeat
5	"AaBb" (case-sensitive)	[] (if case-sensitive; ‘A’ and ‘a’ are different)	Case sensitivity affects the result significantly

Common Fresher Mistake

Mistake	What happens	Fix
Using a plain HashSet/HashMap and expecting output in the string’s original order	Iteration order not guaranteed	Use LinkedHashSet/LinkedHashMap if order matters, or re-scan the original string for the output
Adding a character to the result list every time it’s seen as a duplicate (once per repeat, not once total)	Character appears multiple times in the OUTPUT list too, when it should appear just once	Use a Set for the result (or check before adding) to avoid listing the same duplicate character multiple times

---

Before You Code: Clarify the Contract

Before choosing an algorithm, confirm how null and empty strings should behave, whether comparison is case-sensitive, and whether spaces or punctuation count. Java char values are UTF-16 code units, not always complete human-visible Unicode characters, so international text may require code points or grapheme-aware libraries.

Analogy: Identifying Loyal Mall Shoppers

Imagine you are a security guard tracking people entering a shopping mall gate by gate:

• You want to compile a list of all unique shoppers who entered the mall more than once, listing them in the order they first arrived:
  • The Guest Register (LinkedHashMap): As shoppers walk in, you log their name in a notebook in order of arrival, adding a tick mark for each entry.
  • The Audit (Filtering): At the end of the day, you look down your notebook from top to bottom (preserving their original arrival order):
    • Shopper “Alice” has 1 tick mark. Skip.
    • Shopper “Bob” has 2 tick marks. You write “Bob” on your loyalty list.
    • Shopper “Charlie” has 3 tick marks. You write “Charlie” on your loyalty list (only once, even though he visited three times!).
  • You end up with a clean list of loyal visitors in their first-arrival order!

---

Solution 1 — Frequency Map + Filter (Recommended)

Intuition

This directly extends Q49’s counting logic — instead of just counting how many characters qualify, we collect the actual character values that qualify (count > 1) into a result list, in the order they first appeared.

import java.util.LinkedHashMap;
import java.util.ArrayList;
import java.util.List;

public class FindAllDuplicateChars {
    public static List<Character> findDuplicates(String str) {
        LinkedHashMap<Character, Integer> freq = new LinkedHashMap<>();

// Build frequency map (LinkedHashMap preserves first-seen order)
        for (char ch : str.toCharArray()) {
            freq.put(ch, freq.getOrDefault(ch, 0) + 1);
        }

List<Character> duplicates = new ArrayList<>();
        for (var entry : freq.entrySet()) {
            if (entry.getValue() > 1) {
                duplicates.add(entry.getKey()); // added once per distinct repeating character
            }
        }
        return duplicates;
    }

public static void main(String[] args) {
        System.out.println(findDuplicates("programming")); // [r, g, m]
        System.out.println(findDuplicates("aabbcc"));          // [a, b, c]
        System.out.println(findDuplicates("abcdef"));           // []
    }
}

Output:

[r, g, m]
[a, b, c]
[]

Dry Run (str = “programming”)

Building freq map in first-seen order:
p:1, r:2, o:1, g:2, a:1, m:2, i:1, n:1

Scanning entries (in insertion order):
p -> count=1, skip
r -> count=2 > 1 -> add -> duplicates=[r]
o -> count=1, skip
g -> count=2 > 1 -> add -> duplicates=[r,g]
a -> count=1, skip
m -> count=2 > 1 -> add -> duplicates=[r,g,m]
i -> count=1, skip
n -> count=1, skip

Final: [r, g, m]

Interviewer’s take

This is exactly the expected solution — using LinkedHashMap ensures the output list reflects the order characters first appeared in the string, which is usually the expected (and more useful/predictable) behavior. Each qualifying character is added exactly once, regardless of how many times it actually repeats — an important detail interviewers check for.

Follow-up questions you might get:

• “Why LinkedHashMap instead of HashMap?” → To guarantee the output order matches the string’s natural left-to-right character order, rather than an unpredictable hash-based order.
• “How would you handle case-insensitivity?” → Convert each character to lowercase (or uppercase) before adding it to the frequency map, if 'A' and 'a' should be treated as the same character.
• “What’s the time and space complexity?” → O(n) time (single pass to build the map, plus a pass over at most n map entries), O(k) space where k is the number of distinct characters.

---

📊 Visual Flowchart

graph TD
    Start["Input String str"] --> InitMap["Initialize LinkedHashMap freqMap"]
    InitMap --> Loop1{"For each char ch in str"}
    Loop1 -->|Yes| MapInc["freqMap[ch]++"]
    MapInc --> Loop1
    Loop1 -->|No| InitList["Initialize duplicates List"]
    InitList --> Loop2{"For each entry in freqMap"}
    Loop2 -->|Yes| CheckFreq{"entry.value > 1?"}
    CheckFreq -->|Yes| AddList["duplicates.add(entry.key)"]
    CheckFreq -->|No| NextEntry["Move to next entry"]
    AddList --> NextEntry
    NextEntry --> Loop2
    Loop2 -->|No| End["Return duplicates List"]

---

Final Verdict — Which Solution Should You Give?

• Solution 1 is the standard, expected approach. This is a natural, direct extension of the frequency-counting pattern used throughout this whole family of problems (Q24, Q42, Q44, Q48, Q49) — showing you can chain and adapt a familiar pattern to slightly different requirements is exactly what interviewers want to see.

---

Quick Recap

Approach	Time	Space	Preserves order?
LinkedHashMap + filter	O(n)	O(k) — k = distinct chars	Yes