Problem Description

You are given a string s. Your task is to find the first character in the string that appears only once (non-repeating) and return its index position. If every character in the string appears more than once, return -1.

For example:

• In the string "leetcode", the character 'l' appears at index 0 and is the first non-repeating character, so return 0
• In the string "loveleetcode", the character 'l' appears multiple times, 'o' appears multiple times, but 'v' at index 2 is the first character that appears only once, so return 2
• In the string "aabb", all characters repeat, so return -1

The solution approach counts the frequency of each character in the string using a Counter (hash table). Then it iterates through the string from the beginning, checking each character's count. The first character with a count of exactly 1 is the first non-repeating character, and its index is returned. If no such character exists after checking all positions, -1 is returned.

Intuition

To find the first non-repeating character, we need to know which characters appear only once in the entire string. The key insight is that we must examine the entire string first to determine the frequency of each character before we can identify which one is non-repeating.

Why can't we solve this in a single pass? Consider the string "aab". When we encounter the first 'a' at index 0, we might think it's unique, but we later discover another 'a' at index 1. This shows we need complete frequency information before making any decisions.

The natural approach is to break this into two phases:

1. Count all characters: First pass through the string to build a frequency map. This tells us exactly how many times each character appears.
2. Find the first unique character: Second pass through the string in order, checking each character's frequency. The first character with frequency 1 is our answer.

Why do we need the second pass? Because we want the first non-repeating character by position, not just any non-repeating character. The frequency map doesn't preserve the order of characters in the original string. By iterating through the string again from the beginning and checking against our frequency map, we ensure we return the earliest position where a unique character occurs.

This two-pass approach with O(n) time complexity is optimal because we must examine every character at least once to know their frequencies, and we need to maintain the original order to find the "first" occurrence.

Solution Approach

The implementation uses a hash table to count character frequencies, then performs a linear scan to find the first unique character.

Step 1: Count Character Frequencies

We use Python's Counter from the collections module to create a frequency map:

cnt = Counter(s)

This single line traverses the entire string s and builds a hash table where:

• Keys are the characters in the string
• Values are the number of times each character appears

For example, if s = "leetcode", then cnt would be:

{'l': 1, 'e': 3, 't': 1, 'c': 1, 'o': 1, 'd': 1}

Step 2: Find First Unique Character

We iterate through the string again using enumerate() to track both the index and character:

for i, c in enumerate(s):
    if cnt[c] == 1:
        return i

During this iteration:

• i represents the current index position
• c represents the character at position i
• We check if cnt[c] == 1, meaning this character appears exactly once
• If true, we immediately return the index i since this is the first unique character

Step 3: Handle No Unique Characters

If the loop completes without finding any character with frequency 1:

return -1

Time and Space Complexity:

• Time Complexity: O(n) where n is the length of the string. We traverse the string twice - once to build the frequency map and once to find the first unique character.
• Space Complexity: O(1) or O(k) where k is the number of unique characters. Since we're dealing with lowercase English letters, the space is bounded by 26, making it effectively constant.

The solution is optimal because we must examine every character at least once to determine uniqueness, and the two-pass approach maintains the simplicity while preserving the order requirement.

Example Walkthrough

Let's walk through the solution with the string s = "loveleetcode".

Step 1: Count Character Frequencies

First, we build a frequency map by counting each character:

• l appears at positions 0, 4, 5 → count = 3
• o appears at positions 1, 7 → count = 2
• v appears at position 2 → count = 1
• e appears at positions 3, 6, 8, 11 → count = 4
• t appears at position 9 → count = 1
• c appears at position 10 → count = 1
• d appears at position 12 → count = 1

Our frequency map: {'l': 3, 'o': 2, 'v': 1, 'e': 4, 't': 1, 'c': 1, 'd': 1}

Step 2: Find First Unique Character

Now we iterate through the string from the beginning, checking each character's count:

• Index 0: s[0] = 'l', cnt['l'] = 3 → Not unique (count > 1), continue
• Index 1: s[1] = 'o', cnt['o'] = 2 → Not unique (count > 1), continue
• Index 2: s[2] = 'v', cnt['v'] = 1 → Unique! (count = 1), return 2

We found our answer at index 2. The character 'v' is the first character that appears only once in the string.

Why Two Passes?

Notice that we have other unique characters ('t', 'c', 'd') but they appear later in the string. Without the first pass to count all frequencies, we wouldn't know that 'l' at index 0 actually repeats later. The second pass ensures we return the first unique character by position, which is 'v' at index 2, not just any unique character.

Solution Implementation

Time and Space Complexity

The time complexity is O(n), where n is the length of the string s. This is because:

• Creating the Counter takes O(n) time as it needs to iterate through all characters in the string once
• The enumerate loop iterates through the string once more, which is another O(n) operation
• The lookup operation cnt[c] inside the loop is O(1) for a hash table
• Overall: O(n) + O(n) = O(n)

The space complexity is O(|Σ|), where Σ is the character set. Since the problem deals with lowercase English letters, |Σ| = 26. The Counter (hash table) will store at most 26 key-value pairs, one for each unique lowercase letter that appears in the string. This gives us a constant space complexity of O(26) = O(1) when considering the character set is fixed, or more generally O(|Σ|) when considering variable character sets.

Common Pitfalls

Pitfall 1: Attempting to Use the Counter Keys Directly

A common mistake is trying to iterate through the Counter's keys instead of the original string, which loses the original order:

Incorrect Approach:

def firstUniqChar(self, s: str) -> int:
    char_count = Counter(s)
  
    # Wrong: iterating through counter keys doesn't preserve original order
    for char in char_count:
        if char_count[char] == 1:
            return s.index(char)  # This might not return the FIRST unique character
    return -1

Why it's wrong: The Counter's keys may not maintain the order of first appearance. For example, with s = "loveleetcode", iterating through char_count.keys() might process characters in an arbitrary order, potentially returning the index of 'd' (10) instead of 'v' (2).

Solution: Always iterate through the original string to maintain the order of characters as they appear.

Pitfall 2: Using str.index() After Finding a Unique Character

Incorrect Approach:

def firstUniqChar(self, s: str) -> int:
    char_count = Counter(s)
  
    for char in s:
        if char_count[char] == 1:
            return s.index(char)  # Inefficient and redundant
    return -1

Why it's problematic: While this works correctly, using s.index(char) adds unnecessary overhead. The index() method performs another O(n) search in the worst case, even though we already know the position from our iteration.

Solution: Use enumerate() to track indices during iteration, avoiding the need for an additional search.

Pitfall 3: Modifying the Counter During Iteration

Incorrect Approach:

def firstUniqChar(self, s: str) -> int:
    char_count = Counter(s)
  
    for i, char in enumerate(s):
        if char_count[char] == 1:
            return i
        else:
            # Wrong: modifying the counter during iteration
            del char_count[char]  
    return -1

Why it's wrong: Deleting entries from the Counter while iterating can lead to incorrect results for subsequent characters. If a character appears multiple times, deleting it after the first occurrence would make later occurrences appear to be unique.

Solution: Never modify the frequency map during the search phase. Keep it immutable after the initial count.

Pitfall 4: Not Handling Edge Cases

Incorrect Approach:

def firstUniqChar(self, s: str) -> int:
    # Missing edge case handling
    char_count = Counter(s)
  
    for i, char in enumerate(s):
        if char_count[char] == 1:
            return i

Why it's incomplete: The code doesn't explicitly handle the case where no unique character exists, potentially causing unexpected behavior or errors in some implementations.

Solution: Always include an explicit return statement after the loop to handle the case where no unique character is found:

for i, char in enumerate(s):
    if char_count[char] == 1:
        return i
return -1  # Explicitly handle the no-unique-character case