Short answer
Use a LinkedHashMap<Character,Integer> to count occurrences while preserving insertion order, then return the first key whose count is 1 -- O(n) with one pass to count and one to scan.
Explanation
For a fixed alphabet an int[256] frequency array plus a second pass over the original string works and avoids the map overhead. The key insight is that you need to preserve original order, which a plain HashMap does not.
Common mistakes
- Using nested loops (O(n²)).
- Using HashMap where LinkedHashMap is needed to keep order.