Get Distinct Characters from a String - Java

Category: Easy | Concepts used: HashSet vs LinkedHashSet structures, insertion order preservation, time-space complexity trade-offs

---

Problem Statement

Given a string, return only the distinct (unique) characters — each character should appear only once in the output, preserving their first-seen order.

Input : "banana"      Output: "ban"   (b, a, n — each only once, in first-seen order)
Input : "hello"        Output: "helo"  (repeated 'l' collapsed to one)

Examples (with edge scenarios)

#	Input	Output	Why
1	"banana"	"ban"	b, a, n each appear once, in order of first appearance
2	""	""	Empty string yields empty output
3	"aaaa"	"a"	Collapses duplicates to a single representation
4	"abcabc"	"abc"	Drops recurring copies
5	"Aa"	"Aa"	Case-sensitive characters treated independently

⚠️ Common Beginner Mistake

Mistake	Impact	Fix
Using a plain HashSet and expecting insertion order to be preserved	Characters outputted in a scrambled order due to internal bucket hashing	Use LinkedHashSet to guarantee insertion order
Concatenating characters in a String loop	Slower runtime due to constant heap allocations	Use StringBuilder for buffer append operations

---

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 Travel Journal Stamp Collection

Imagine you are traveling through various countries (the characters in the string):

• Every time you enter a country, you want to get a unique stamp in your travel journal:
  • Solution 1 (LinkedHashSet - Chronological): You stamp the pages as you visit. To avoid duplicates, if you return to a country you already visited, you skip stamping it again. Your journal shows every unique country, in the exact chronological order you first visited them ("ban").
  • Solution 2 (HashSet - Bucket): You place all unique stamps in a jar. When you dump them out on a table, they scatter in a completely random arrangement ("abn"). You have the unique set, but the chronological sequence is lost.
  • Solution 3 (TreeSet - Alphabetical Index): You organize your stamps alphabetically in a file cabinet ("abn"). They are ordered by letter value, not by time of visit.

---

Solution 1 — Using LinkedHashSet (Recommended, Preserves Order)

This is the standard, order-preserving set approach.

Intuition

A LinkedHashSet preserves the insertion order of elements because it maintains a doubly-linked list running through all of its entries. This solves the duplicate elimination and sequence preservation in a single loop.

import java.util.LinkedHashSet;

public class DistinctCharsOrdered {
    public static String distinctChars(String str) {
        if (str == null || str.isEmpty()) {
            return str;
        }

LinkedHashSet<Character> seen = new LinkedHashSet<>();
        StringBuilder result = new StringBuilder();

for (int i = 0; i < str.length(); i++) {
            char ch = str.charAt(i);
            // LinkedHashSet.add() returns true if the element was not already present
            if (seen.add(ch)) {
                result.append(ch); // Append in order of first discovery
            }
        }
        return result.toString();
    }

public static void main(String[] args) {
        System.out.println(distinctChars("banana")); // "ban"
        System.out.println(distinctChars("hello"));    // "helo"
        System.out.println(distinctChars(""));          // ""
        System.out.println(distinctChars("aaaa"));       // "a"
    }
}

Output:

ban
helo

a

Dry Run (str = “banana”)

i = 0: 'b' -> seen.add('b') returns true -> result = "b", seen = {b}
i = 1: 'a' -> seen.add('a') returns true -> result = "ba", seen = {b, a}
i = 2: 'n' -> seen.add('n') returns true -> result = "ban", seen = {b, a, n}
i = 3: 'a' -> seen.add('a') returns false (duplicate) -> skipped
i = 4: 'n' -> seen.add('n') returns false (duplicate) -> skipped
i = 5: 'a' -> seen.add('a') returns false (duplicate) -> skipped
Result = "ban"

---

Solution 2 — Using a Plain HashSet (Only if Order is Irrelevant)

This approach deduplicates values without sequence guarantees.

Intuition

If the relative sequence of characters does not matter, a plain HashSet is slightly faster since it does not have the linked list overhead.

import java.util.HashSet;

public class DistinctCharsUnordered {
    public static String distinctChars(String str) {
        if (str == null || str.isEmpty()) {
            return str;
        }

HashSet<Character> seen = new HashSet<>();
        StringBuilder result = new StringBuilder();

        for (int i = 0; i < str.length(); i++) {
            char ch = str.charAt(i);
            if (seen.add(ch)) {
                result.append(ch);
            }
        }
        return result.toString(); // Order is NOT guaranteed to match input order
    }

public static void main(String[] args) {
        System.out.println(distinctChars("banana")); // Output layout may vary: "abn"
    }
}

---

📊 Visual Flowchart

graph TD
    Start["Input String S"] --> NullCheck{"S is null?"}
    NullCheck -->|Yes| RetNull["Return Null"]
    NullCheck -->|No| Init["Initialize LinkedHashSet seen, StringBuilder sb"]
    Init --> Loop{"i < S.length()?"}
    Loop -->|Yes| Fetch["ch = S.charAt(i)"]
    Fetch --> CheckSet{"seen.contains(ch)?"}
    CheckSet -->|Yes| Skip["i++"]
    CheckSet -->|No| Add["seen.add(ch)"]
    Add --> Append["sb.append(ch)"]
    Append --> Skip
    Skip --> Loop
    Loop -->|No| Convert["sb.toString()"]
    Convert --> End["Return result"]

---

Interviewer Insights

This is a core question checking for clear awareness of Java Collections implementation rules.

Follow-up questions you might get:

• “What are the internal differences between HashSet, LinkedHashSet, and TreeSet?” →
  • HashSet is backed by a HashMap. It offers (O(1)) lookup/insertion but does not preserve any order.
  • LinkedHashSet is backed by a hash table and a doubly-linked list. It offers (O(1)) operations and guarantees insertion order.
  • TreeSet is backed by a Red-Black tree structure. It sorts elements in natural order (alphabetical) but operations scale at (O(\log N)) time complexity.
• “How could you write this without using collections at all?” → You can use a boolean array of size 256 (assuming ASCII) to track character state, which takes (O(1)) space:

  public static String distinctCharsNoCollection(String str) {
      if (str == null) return null;
      boolean[] seen = new boolean[256];
      StringBuilder sb = new StringBuilder();
      for (int i = 0; i < str.length(); i++) {
          char ch = str.charAt(i);
          if (!seen[ch]) {
              seen[ch] = true;
              sb.append(ch);
          }
      }
      return sb.toString();
  }

---

Quick Recap

Collection	Time Complexity	Auxiliary Space Complexity	Order Guaranteed?	Interview Signal
LinkedHashSet	(O(N))	(O(N))	Yes (insertion order)	Preferred, optimal order preservation
HashSet	(O(N))	(O(N))	No	Good, but order may get scrambled
Boolean Array	(O(N))	(O(1)) (size 256 is constant)	Yes (insertion order)	Advanced optimization, avoids collections entirely