Find the First Non-Repeating Character
- mosesg1123
- Apr 10
- 4 min read
Updated: 7 days ago
Alright, you're in a technical interview and you've just been given the question:
“Find the index of the first non-repeating character in a string. If there isn’t one, return -1.”
Let's approach this question, out loud, step by step, using the framework I rely on in every interview.
1. Clarify Requirements Before Jumping Into Code
Let me make sure I fully understand what’s being asked.
We're given a string — let’s say "loveleetcode" — and we’re supposed to find the index of the first character that only appears once in the string. So, in that case, 'v' is the first unique character and its index is 2.
A few clarifying questions:
Are uppercase and lowercase characters considered different? (Assuming yes unless told otherwise)
Can the string be empty? If so, should I return -1? (I’ll handle that as an edge case)
Cool. Once we’ve nailed the input/output expectations, I feel good moving on.
2. Identify the Category of the Question
Hmm. This feels like a string traversal problem, but more specifically, it’s about character frequency — that usually screams hash map to me.
It’s not about sorting or backtracking, and it doesn’t seem like dynamic programming is needed. It’s probably in the “hash table + string manipulation” category, with a side of indexing.
3. Consider a Brute-Force Approach to Understand the Problem
Let me start with the most naive approach just to feel things out.
I could loop through each character and, for each one, scan the rest of the string to count how many times it appears. The first one with a count of 1 is our answer.
That would be something like:
for i in range(len(s)):
if s.count(s[i]) == 1:
return i
But count() is O(n), and we’re doing that up to n times, so this would be O(n²). Definitely not efficient for longer strings, but it confirms that the logic is sound.
4. Brainstorm More Solutions
Okay, let’s do better.
Since we’re essentially counting how often each character appears, I can do that with a single pass using a hash map (or a fixed-size array if we assume lowercase letters).
Then, I can do a second pass through the string and return the index of the first character with a count of 1.
So, two passes — one to build the frequency map, one to find the result.
That would be O(n) time and O(1) space if we assume the alphabet size is constant — or O(n) if we consider input-dependent characters.
5. Discuss Trade-Offs Between Your Solutions
The brute-force approach is simple and readable but too slow for large inputs.The two-pass solution with a hash map is much more efficient, but uses extra space.
If space were a serious constraint, I might consider optimizing further — but for interview purposes, the hash map solution is fast and easy to reason about, which makes it ideal.
Also, using a fixed-size array of 26 for lowercase characters could be a space optimization if the character set is guaranteed.
6. Write Pseudocode to Structure Your Thoughts
Let me sketch this out in pseudocode before writing the full code:
function firstUniqChar(s):
create empty hash map char_count
for each character c in s:
increment char_count[c] by 1
for index i, character c in s:
if char_count[c] == 1:
return i
return -1
Looks clean. Ready to translate into actual code now.
7. Consider Edge Cases
Let’s think through anything that might trip us up:
Empty string: return -1
All characters repeated: return -1
First character is the only unique one: test that
Last character is unique: test that
Input with only one character: should return index 0
Yup — good to go.
8. Write Full Code Syntax
Here’s how that would look in Python:
def firstUniqChar(s: str) -> int:
from collections import Counter
char_count = Counter(s)
for i, c in enumerate(s):
if char_count[c] == 1:
return i
return -1
9. Test Your Code
Let’s run some test cases.
print(firstUniqChar("leetcode")) # 0 ('l')
print(firstUniqChar("loveleetcode")) # 2 ('v')
print(firstUniqChar("aabb")) # -1
print(firstUniqChar("z")) # 0
print(firstUniqChar("")) # -1
print(firstUniqChar("xxyyz")) # 4 ('z')
All tests pass. Clean, readable, and efficient.
Key Lessons
Here are a few takeaways and tricks from this problem that you can carry into future interviews:
Character Frequency = Hash Map Time Any time a problem involves counting how often things appear—words, numbers, letters—think hash map (or frequency table). It’s often the most efficient way to go.
Two Passes? Totally Fine. Don’t shy away from doing two passes through the input if it simplifies your logic. One pass to collect data, the second to make decisions—that’s a common and effective strategy.
When in Doubt, Brute It Out (First) If you're stuck, try solving a tiny version of the problem with brute-force logic. It helps anchor your understanding and often reveals the shape of a better solution.
Index-Based Returns? Track Carefully. When you're expected to return an index instead of a value, pay attention to how you're looping.
Test for the Weird Stuff Don’t forget to test edge cases: empty strings, repeated characters, only one character, and non-repeating chars at the start or end. These help you validate your assumptions and catch bugs early.
Hash Map vs. Array If the character set is limited (like lowercase English letters), you can optimize further by using an array of fixed size (26). It’s fast and space-efficient, though less readable than a dict or Map.
Feeling stuck in an interview? Ask yourself: “What data do I need to solve this problem?”If the answer involves counts or lookups, that’s a strong hint a hash map is the way to go.
Comments