First Non Repeating Character HashMap
Fast recall
Quick revision
Core answer
HashMap (or int[26]). Second pass: walk the string in order and return the first character whose count is 1. That's O(n) time and O(1) space for a fixed alphabet. A single LinkedHashMap pass also works since it preserves insertion order.Whether you build a frequency map then scan in original order, keeping it O(n)
Scanning the rest of the string for each character (O(n^2)) or losing original order
Note int[26] gives O(1) space, and that the second pass must follow the original order
Interview-ready guide
Interview answer
I'd solve this with frequency counting in two passes, which keeps it linear.
In the first pass I walk the string and count how many times each character appears. For lowercase English letters I use an integer array of size twenty-six, mapping each character to a bucket by subtracting the character a, which gives me constant space. If the alphabet could be anything, I'd use a HashMap from character to count instead.
In the second pass, I walk the original string again, in order, and I return the first character whose count is exactly one. The detail that really matters here is that the second pass iterates over the string, not over the map. A HashMap has no ordering, so if I looked for the unique character by iterating the map, I might not get the first one in the original string.
By scanning the string itself, the first character I hit with a count of one is guaranteed to be the answer. This is O of n time, since each pass is linear, and O of one space for a fixed alphabet. The brute-force alternative, where for each character I scan the rest of the string to see if it repeats, is O of n squared, so I avoid that.
I also handle the case where every character repeats by returning a sentinel value, like an underscore or minus one, to signal there's no unique character. If keys were arbitrary objects and I wanted a single pass, a LinkedHashMap would let me preserve insertion order while counting.
First Non Repeating Character HashMap
Direct Answer
Use frequency counting in two passes. First pass: count each character into a HashMap<Character,Integer> (or int[26]). Second pass: walk the string in order and return the first character whose count is 1. That's O(n) time and O(1) space for a fixed alphabet. A single LinkedHashMap pass also works since it preserves insertion order.
Deep Dive & Architecture
Finding the first unique character needs two separate facts: each character's total count and its position in the original string. A frequency map gives the first fact; a second scan of the string preserves the second.
Worked example: swiss
The first pass produces s=3, w=1, and i=1. Iterating over the map cannot decide whether w or i appeared first because HashMap has no insertion-order guarantee. Scanning swiss again checks s and then w; count 1 at w makes it the answer at index 1.
If no count equals one, return the contract's chosen value, such as -1 for an index or an empty optional for a character. State whether matching is case-sensitive and whether spaces count. For lowercase English letters, an int[26] can replace the map. For general text, a map is more flexible; full Unicode handling may require iterating code points rather than UTF-16 char values.
The two scans are still O(n), and the map uses O(k) space for k distinct characters. A LinkedHashMap can remember first insertion order, but the straightforward two-pass solution is usually clearer and also returns the exact original index.
Code Example
char firstUniq(String s) {
int[] count = new int[26];
for (char c : s.toCharArray()) count[c - 'a']++; // pass 1
for (char c : s.toCharArray()) // pass 2: original order
if (count[c - 'a'] == 1) return c;
return '_'; // sentinel: no unique character
}
// s = "leetcode"
// counts: l1 e3 t1 c1 o1 d1
// pass 2: 'l' count 1 -> return 'l'
// s = "aabb" -> pass 2 finds none -> '_'
Common Mistakes & Pitfalls
- O(n^2) inner scan: re-scanning the string per character; count once instead.
- Iterating the map in pass 2: HashMap has no order, so you'd lose 'first'; iterate the string.
- NPE / default: with a HashMap use
getOrDefault; withint[]no null risk. - No-result case: return a sentinel (
'_'or-1) when every character repeats.
Check your understanding
Answer these without looking back at the article.
- How do you use a HashMap to solve the frequency counting pattern?
- What happens when two keys produce the same hash code? How does a HashMap handle it?
- How does a HashMap work internally in Java?
Looking for a structured roadmap?
Every module on this page is also part of the full Java backend interview track.