Find first non-repeated character.

Hook: Interviewers love this one because it checks whether you can keep the original order while counting at the same time — a very common coding pattern.

Question: Find first non-repeated character in a string.

Answer: I would scan the string once to count each character, then scan again in the original order and return the first character whose count is 1. This is simple, fast, and avoids missing the left-to-right order. If no such character exists, I would return null or a special marker, depending on the interviewer's requirement.

Interview-Ready Answer: I’d use a frequency map and preserve insertion order. First I count every character in one pass, then I walk the entries in the same order the characters appeared and return the first one with count 1. That gives me O(n) time and O(k) space, and if the string can contain emoji or other non-BMP characters, I’d switch from char iteration to code points.

What the problem is really asking

“First” means leftmost in the original string, not smallest alphabetically. A character is “non-repeated” if it appears exactly once in the whole input. In Java, the clean interview solution usually counts characters with a LinkedHashMap because it keeps the order in which keys were first seen.

How it works under the hood

1. Read the string from left to right and add each character to a map.
2. For each character, increase its count from 0 to 1, 2, and so on.
3. Because the map remembers insertion order, the first time you saw a character is also the first place you will revisit it later.
4. After counting, walk the map entries in order and return the first entry whose count is 1.
5. If every count is greater than 1, return null or whatever sentinel your API requires.

Why this is better than the obvious alternatives

A brute-force solution checks each character with indexOf and lastIndexOf, but that can become O(n²) because each character may trigger more scanning. A plain HashMap counts correctly, but it does not guarantee iteration order, so you cannot safely use it to find the first unique character. LinkedHashMap gives you both counting and stable order.

Performance and edge cases

• Time: O(n) because each character is processed a constant number of times.
• Space: O(k), where k is the number of distinct characters.
• Empty or null input: return null immediately.
• No unique character: also return null or a sentinel.
• Unicode detail: char in Java is a UTF-16 code unit, so emoji may need codePoints() instead of simple character iteration.

Memory-wise, think of it like a ticket line: you stamp each person once, then replay the line from the front and pick the first person who only got one stamp.

Real-World Example: Imagine a checkout service that validates a customer reference code typed into a web form. The service wants to highlight the first character that appears only once so support can spot typos or suspicious patterns quickly.

One bug I have seen in code reviews is using a HashMap and then looping through its keys, assuming they come out in the same order they were inserted. In production, that can make the chosen character look random across JVM runs, which is awful for debugging and user trust.

• Symptoms: different servers flag different characters for the same input.
• Logs: “first unique char = r” on one node, “first unique char = h” on another.
• User impact: inconsistent validation errors and support tickets that are hard to reproduce.

Follow-up & Tricky Questions:

• Why use LinkedHashMap instead of HashMap? Because HashMap does not guarantee order, and this problem depends on the first character seen. LinkedHashMap preserves insertion order, so the first unique entry can be found safely.
• Can you do it in one pass? Usually not cleanly, because you do not know whether a character is truly unique until you have seen the whole string. You can maintain extra state, but the standard two-pass approach is simpler and clearer.
• What is the time and space complexity? The standard solution is O(n) time and O(k) space, where k is the number of distinct characters. Each character is counted once and checked once.
• How would you return the index instead of the character? Keep the same counting logic, then scan the original string again and return the first index whose character has count 1. That keeps the result aligned with the original order.
• How would you handle Unicode emoji? Do not rely on char alone, because it is a UTF-16 code unit. Use s.codePoints() and a map keyed by code point if the input can contain supplementary characters.
• Tricky: Is HashMap iteration order stable in practice? No. It can appear stable in small tests, but the Java API does not promise any order, so you must not depend on it.
• Tricky: Is indexOf plus lastIndexOf acceptable? It works for correctness, but it can be O(n²) in the worst case because you repeat scans for many characters. Interviewers usually prefer the O(n) counting approach.
• Tricky: Does whitespace count as a character? Yes, unless the problem explicitly says to ignore spaces. Always clarify whether you should include spaces, punctuation, and case differences.

Common Mistakes:

• Using HashMap and assuming the keys come back in input order; the correction is to use LinkedHashMap or scan the string again after counting.
• Returning the first character that appears once in the map but not in the original order; the correction is to preserve left-to-right order explicitly.
• Writing a nested-loop or repeated indexOf/lastIndexOf solution; the correction is to use a frequency map for O(n) time.
• Forgetting edge cases like null, empty strings, or “no unique character”; the correction is to define the return value up front.

Memory Hook: Count it, then line it up. First you stamp every character, then you walk the line from left to right and pick the first person with only one stamp.

Cheat Sheet:

• Problem: find the leftmost character with frequency 1.
• Best general Java answer: LinkedHashMap + two passes.
• Time: O(n). Space: O(k).
• HashMap counts well, but does not preserve order.
• Return null or a sentinel when nothing is unique.
• For emoji or full Unicode, prefer code points over char.

Practice Tasks:

• Write the same function for lowercase English letters only using int[26].
• Change the method to return the index of the first non-repeated character.
• Upgrade the solution to handle Unicode code points with s.codePoints().