Remove Duplicate Characters from a String - Java

@Note: This is categorized as “Difficult” because candidates frequently fail to realize that Java Strings are immutable and struggle to perform this transformation efficiently without O(N^2) replacements.

---

Category: Difficult | Concepts used: Order-preserving deduplication

---

Problem Statement

Given a string, remove duplicate characters so each character appears only once, keeping the first occurrence and its original position order.

Input : "programming"      Output: "progamin"

Note: This is related to (but distinct from) Q19 (“get distinct characters”) — same underlying technique, phrased as a transformation of the original string rather than building a fresh character list.

Examples (with edge scenarios)

#	Input	Output	Why
1	"programming"	"progamin"	Each letter kept only at its first occurrence
2	"" (empty)	""	Nothing to process
3	"aaaa"	"a"	All same character collapses to one
4	"abcabc"	"abc"	Second half entirely removed as duplicates
5	"a b a" (with spaces)	"a b"	The space character itself is also subject to deduplication (treated just like any other character) unless told otherwise

Common Fresher Mistake

Mistake	What happens	Fix
Using a plain HashSet and expecting order preservation	Output characters could come out in a scrambled, unpredictable order	Use LinkedHashSet to preserve first-seen order
Trying to modify the string “in place”	Not possible — Java Strings are immutable	Build a NEW string (via StringBuilder) containing only the first occurrence of each character

---

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: The Exclusive Lounge Guest List

Imagine you are a security guard standing at the door of an exclusive VIP lounge:

• Guests are arriving in a queue (characters in the string). You want to admit them into the lounge (StringBuilder) in the exact order they arrive:
  • The Clipboard (LinkedHashSet): You have a clipboard register of guests already admitted.
  • When the first guest, “A”, arrives: you check your list. Since “A” is not listed, you write “A” on your list and let them enter the lounge.
  • When the next guest, “B”, arrives: you do the same.
  • When another guest, “A”, arrives: you check your clipboard. Since “A” has already been admitted, you politely turn them away (skip them).
  • The lounge ends up containing a clean list of unique guests in the exact order they first arrived!

---

Solution 1 — Using LinkedHashSet + StringBuilder (Recommended)

Intuition

Walk through the string once, character by character. Keep a LinkedHashSet as a “have I already kept this character?” tracker. For each new character, if the set doesn’t already contain it, add it to both the set (to remember it for future checks) and to the result string; if it’s already in the set, skip it entirely (it’s a repeat we don’t want to keep).

import java.util.LinkedHashSet;

public class RemoveDuplicateChars {
    public static String removeDuplicates(String str) {
        LinkedHashSet<Character> seen = new LinkedHashSet<>();
        StringBuilder result = new StringBuilder();

for (char ch : str.toCharArray()) {
            if (!seen.contains(ch)) {
                seen.add(ch);
                result.append(ch); // keep only the first occurrence
            }
            // if already seen, simply skip (don't append again)
        }
        return result.toString();
    }

public static void main(String[] args) {
        System.out.println(removeDuplicates("programming")); // progamin
        System.out.println(removeDuplicates("aaaa"));           // a
        System.out.println(removeDuplicates(""));                // (empty)
        System.out.println(removeDuplicates("abcabc"));           // abc
    }
}

Output:

progamin
a
(empty string)
abc

Dry Run (str = “abcabc”)

seen={}, result=""

'a' -> not in seen -> seen={a}, result="a"
'b' -> not in seen -> seen={a,b}, result="ab"
'c' -> not in seen -> seen={a,b,c}, result="abc"
'a' -> already in seen -> skip
'b' -> already in seen -> skip
'c' -> already in seen -> skip

Final: "abc"

Interviewer’s take

This is exactly the expected solution — combining a LinkedHashSet (for O(1) “have I seen this?” lookups while preserving order) with a StringBuilder (for efficient string building) is the ideal combination for this problem. This same pattern — “seen-tracker + build result” — is reusable across many similar deduplication problems.

Follow-up questions you might get:

• “Why not just use LinkedHashSet alone, without the separate StringBuilder?” → You could build the result by iterating the final LinkedHashSet directly (since it preserves order) instead of using a separate StringBuilder, but doing both together in one pass (as shown) avoids a second iteration and slightly clarifies intent (the Set is for tracking, the builder is for output).
• “What’s the time and space complexity?” → O(n) time (single pass, O(1) average set operations), O(k) space for the set and result, where k is the number of distinct characters.
• “How would you handle case-insensitivity (treating ‘A’ and ‘a’ as duplicates)?” → Add a normalized (e.g., lowercased) version of each character to the seen set for the lookup check, while still appending the original-case character to the result — this preserves the original casing in the output while still correctly detecting case-insensitive duplicates.

---

📊 Visual Flowchart

graph TD
    Start["Input String str"] --> Init["Initialize LinkedHashSet seen<br>Initialize StringBuilder result"]
    Init --> Loop{"i < str.length?"}
    Loop -->|Yes| CheckSeen{"seen.contains(str[i])?"}
    CheckSeen -->|No| Add["seen.add(str[i])<br>result.append(str[i])"]
    CheckSeen -->|Yes| Skip["Skip (Duplicate)"]
    Add --> Next["i++"]
    Skip --> Next
    Next --> Loop
    Loop -->|No| End["Return result.toString()"]

---

Final Verdict — Which Solution Should You Give?

• Solution 1 is the standard, expected, and essentially only reasonable approach for this problem — it’s efficient, readable, and correctly preserves order. There isn’t a meaningfully “worse but valid” alternative worth presenting separately here, similar to a few other frequency-map-style problems in this series.

---

Quick Recap

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