Problem Statement
Given a string s, find and return the first non-repeating character in it. If every character repeats, return None (or -1 in languages that prefer numeric values).
Input / Output Format
Input: A single string s (lowercase and/or uppercase letters; may include digits and symbols).
Output: The first non-repeating character (as a single character) or None / -1 if no such character exists.
Constraints
1 ≤ len(s) ≤ 10^6 (be mindful of time & space).- Characters can be any printable ASCII characters; solution should be case-sensitive (i.e., 'A' != 'a').
- Expected optimal time:
O(n), extra space: O(k) where k is number of unique characters.
Examples
| Input |
Output — Explanation |
s = "swiss" |
'w' — characters: s(3 times), w(1), i(1); first non-repeating scanning left to right → 'w'. |
s = "aabbcc" |
None — every character repeats. |
s = "leetcode" |
'l' — 'l' occurs once and is the first unique character. |
s = "aAb" |
'a' — case-sensitive: 'a' and 'A' are different. |
Sample Test Cases (copy & run)
# Test case 1
Input: "swiss"
Output: 'w'
# Test case 2
Input: "aabbcc"
Output: None
# Test case 3
Input: "leetcode"
Output: 'l'
# Test case 4
Input: "aAb"
Output: 'a'
Hints (don't peek!)
- Use a hash-map / dictionary to count frequencies of characters in one pass.
- Scan the string a second time and return the first character with frequency 1.
- Alternatively, record the index of first occurrence alongside counts so you can determine the first unique in a single pass over the map.
What to Compare
Include both a brute-force approach (O(n^2)) for clarity and the hashing-based optimized approach (O(n)). Discuss time & space trade-offs.
Follow-ups / Variations (Great for interviews)
- Return the index of the first non-repeating character instead of the character itself.
- Find the first non-repeating character in a stream (characters arriving one by one).
- Find all characters that occur exactly once, preserving their original order.
Top 10 Common Interview Questions on Hashing
- Explain how a hash table works and its average/worst-case complexities.
- How do you handle collisions in a hash table? Compare chaining vs. open addressing.
- What is a good hash function? What properties should it have?
- Difference between Python’s
dict and set — how are they implemented internally?
- Implement Two Sum problem using hashing. Complexity analysis?
- Find the longest substring without repeating characters using hashing.
- How to detect if an array contains duplicates using hashing?
- Explain load factor in hashing and why resizing is needed.
- How does hashing differ from encryption?
- Real-world use cases of hashing (caches, compilers, databases, password storage).
Footer
Difficulty: Easy → Medium. Topic: Hashing / Frequency Counting.