algoadvance

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

Example 1:

Input: s = "leetcode"
Output: 0

Example 2:

Input: s = "loveleetcode"
Output: 2

Example 3:

Input: s = "aabb"
Output: -1

Clarifying Questions

  1. Can the string be empty?
    • Yes, if the string is empty, return -1.
  2. Can there be uppercase and lowercase letters in the string?
    • Assume that the string consists of only lowercase English letters.
  3. What is the maximum length of the input string?
    • The length of the string can go up to 10^5.

Strategy

To solve this problem efficiently, we can:

  1. Use a dictionary to count the occurrences of each character in the string.
  2. Iterate through the string a second time to find the first character that has a count of 1 in the dictionary.

Code

def firstUniqChar(s: str) -> int:
    # Step 1: Count the occurrences of each character
    char_count = {}
    for char in s:
        if char in char_count:
            char_count[char] += 1
        else:
            char_count[char] = 1
    
    # Step 2: Find the index of the first unique character
    for index, char in enumerate(s):
        if char_count[char] == 1:
            return index
    
    # Return -1 if there is no unique character
    return -1

# Test cases
print(firstUniqChar("leetcode"))      # Output: 0
print(firstUniqChar("loveleetcode"))  # Output: 2
print(firstUniqChar("aabb"))          # Output: -1

Time Complexity

  1. Step 1 (Count characters): This takes O(n) time where n is the length of the string.
  2. Step 2 (Find first unique character): This also takes O(n) time.

Thus, the overall time complexity is O(n). The space complexity is also O(n) due to the dictionary used to store character counts.

This approach ensures we find the first unique character efficiently even for large input sizes up to the order of (10^5).

Try our interview co-pilot at AlgoAdvance.com