Find the First Non-Repeating Character in a String - Java

@Note: This is categorized as “Difficult” because it requires understanding the subtle order-preservation details of HashMap vs LinkedHashMap, which are common failure points in interviews.

---

Category: Difficult | Concepts used: Frequency map, order-preserving lookup

---

Problem Statement

Given a string, find the first character that appears exactly once.

Input : "swiss"      Output: 'w'   ('s' and 'i' repeat, 'w' is the first appearing exactly once)

Note: This is the string-character version of Q44 (which worked on array elements) — same core pattern, applied to characters in a string. Also the direct counterpart to Q42 (“first REPEATING character”) — here we want the opposite condition.

Examples (with edge scenarios)

#	Input	Output	Why
1	"swiss"	'w'	's' repeats (index 0,3), 'w' (index 1) is the first with count 1
2	"" (empty)	None	No characters at all
3	"aabbcc" (all repeat)	None	No character appears exactly once
4	"z" (single char)	'z'	Trivially the first (and only) non-repeating character
5	"aabbc"	'c'	Only 'c' appears exactly once, and it’s at the end

Common Fresher Mistake

Mistake	What happens	Fix
Iterating over a plain HashMap’s keys instead of the original string for the second pass	Order not guaranteed to match the string’s actual character order	Always re-scan the original string in the second pass, not the map’s key set
Trying to solve this in a single pass without first knowing full counts	Can’t know if a character will repeat LATER in the string during a single forward scan	Two passes are necessary: one to count, one to find the first with count 1

---

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 Unique Document Verification

Imagine you are auditing a pile of submitted documents (characters in the string) in the order they were submitted:

• You want to find the earliest document that is completely unique (has no duplicates at all):
  • Pass 1 (The Tally Sheet): As you read each document, you log a tick count next to the sender’s name on a registry sheet.
  • Pass 2 (The Audit): Once you have counted all documents, you go back through the stack from top to bottom (in order of submission):
    • Document 1 is from “Sender S”, which has a total tally of 2 on your registry. Skip.
    • Document 2 is from “Sender W”, which has a total tally of exactly 1 on your registry.
  • You immediately stop your audit and declare Sender W’s document as the first non-repeating submission!

---

Solution 1 — Frequency Map + Second Pass Over Original String (Recommended)

Intuition

Exactly the same two-pass pattern as Q44 (first non-repeating array element) and Q42 (first repeating character) — build a complete frequency count first (since you can’t know if a character repeats without seeing the whole string), then re-scan the original string in order and return the first character whose count is exactly 1.

import java.util.HashMap;

public class FirstNonRepeatingChar {
    public static Character firstNonRepeating(String str) {
        HashMap<Character, Integer> freq = new HashMap<>();

// Pass 1: build frequency counts
        for (char ch : str.toCharArray()) {
            freq.put(ch, freq.getOrDefault(ch, 0) + 1);
        }

// Pass 2: scan original string in order, return first with count == 1
        for (char ch : str.toCharArray()) {
            if (freq.get(ch) == 1) {
                return ch;
            }
        }
        return null; // no non-repeating character found
    }

public static void main(String[] args) {
        System.out.println(firstNonRepeating("swiss")); // w
        System.out.println(firstNonRepeating("aabbcc")); // null
        System.out.println(firstNonRepeating("aabbc"));   // c
    }
}

Output:

w
null
c

Dry Run (str = “swiss”)

Pass 1 - freq map:
freq = {s:2, w:1, i:1}

Pass 2 - scan in order:
's' -> freq.get('s')=2, not 1 -> skip
'w' -> freq.get('w')=1 -> MATCH! -> return 'w'

Interviewer’s take

This is exactly the expected solution — a direct application of the “count first, then re-scan in order” pattern that’s now familiar from several earlier problems. Interviewers who’ve already asked you the “first repeating character” question (Q42) often follow up with this exact problem to see if you can quickly adapt the same pattern with a small condition flip.

Follow-up questions you might get:

• “How is this different from ‘first repeating character’?” → Same exact structure, just check count == 1 instead of count > 1.
• “Can you do this in a single pass using a LinkedHashMap?” → leads to Solution 2.

---

Solution 2 — Using LinkedHashMap (Slightly More Elegant, Still Two Logical Steps)

Intuition

A LinkedHashMap preserves insertion order automatically, so once we build the frequency map (still requires a full pass to know final counts), we can iterate the map itself (not the string again) and trust that its order matches the string’s first-occurrence order — saving us from needing to explicitly re-scan the original string.

import java.util.LinkedHashMap;

public class FirstNonRepeatingCharLinkedMap {
    public static Character firstNonRepeating(String str) {
        LinkedHashMap<Character, Integer> freq = new LinkedHashMap<>();

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

for (var entry : freq.entrySet()) {
            if (entry.getValue() == 1) {
                return entry.getKey(); // first (in insertion order) with count 1
            }
        }
        return null;
    }

public static void main(String[] args) {
        System.out.println(firstNonRepeating("swiss")); // w
    }
}

Output:

w

Interviewer’s take

A nice, slightly more “elegant” variant — avoids the explicit second pass over the string by relying on LinkedHashMap’s ordering guarantee instead. Functionally equivalent to Solution 1; either is a strong answer. Worth mentioning the trade-off: LinkedHashMap has marginally more memory overhead than a plain HashMap due to maintaining the internal linked list for ordering.

---

📊 Visual Flowchart

graph TD
    Start["Input String str"] --> Pass1["Pass 1: Count Frequencies"]
    Pass1 --> Loop1{"i < str.length?"}
    Loop1 -->|Yes| MapInc["freqMap[str[i]]++"]
    MapInc --> Next1["i++"]
    Next1 --> Loop1
    Loop1 -->|No| Pass2["Pass 2: Scan in original order"]
    Pass2 --> Loop2{"j < str.length?"}
    Loop2 -->|Yes| CheckFreq{"freqMap[str[j]] == 1?"}
    CheckFreq -->|Yes| RetChar["Return str[j]"]
    CheckFreq -->|No| Next2["j++"]
    Next2 --> Loop2
    Loop2 -->|No| RetNull["Return null"]

---

Final Verdict — Which Solution Should You Give?

• Both solutions are equally strong — Solution 1 (re-scan original string) is perhaps the more universally understood approach; Solution 2 (LinkedHashMap) is a nice, slightly more compact alternative.
• The core insight — “two passes are unavoidable, because you can’t know if something repeats without seeing everything first” — is the real point being tested here.

---

Quick Recap

Approach	Time	Space	Interview Signal
HashMap + re-scan original string	O(n)	O(n)	Standard, clear
LinkedHashMap + scan map entries	O(n)	O(n)	Slightly more elegant