Given a string s, find the first non-repeating character in it and return its index. If it does not exist, return -1.

  • The string s will only contain lowercase English letters.
  • 1 <= s.length <= 10^5

Example 1:

Input: s = "leetcode"
Output: 0

Example 2:

Input: s = "loveleetcode"
Output: 2

Example 3:

Input: s = "aabb"
Output: -1

Solution

The problem asks us to find the index of the first character that appears only once in the string. We can solve this efficiently using a frequency map.

Approach:

  • Frequency Count: Iterate through the string once to build a frequency map (or an array of size 26 for English lowercase letters) that stores the count of each character.
  • Find First Unique: Iterate through the string a second time. For each character at its current index, check its count in the frequency map. The first character encountered with a count of 1 is our answer. Return its index.
  • No Unique Character: If the second iteration completes without finding any character with a count of 1, it means no unique character exists. In this case, return -1.

This two-pass approach ensures we find the first unique character because we iterate through the string in order in the second pass.

Python Solution:

from collections import Counter

def firstUniqChar(s: str) -> int:
    # Step 1: Count character frequencies
    char_counts = Counter(s)
    
    # Step 2: Iterate through the string to find the first character with a count of 1
    for i, char in enumerate(s):
        if char_counts[char] == 1:
            return i
            
    # Step 3: If no unique character is found, return -1
    return -1