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

  • Constraints:

    • s consists of only lowercase English letters.
    • 1 <= s.length <= 10^5

  • Examples:

Input: s = "leetcode"
Output: 0

Input: s = "loveleetcode"
Output: 2

Input: s = "aabb"
Output: -1

Solution

  • Approach: We can solve this by using a frequency map (or hash map/array) to store the counts of each character. After counting, we iterate through the string again to find the first character with a count of one.

  • Detailed Steps:

    1. Initialize a frequency array (e.g., of size 26 for lowercase English letters) or a hash map to store the count for each character.
    2. First Pass: Iterate through the input string s. For each character encountered, increment its corresponding count in the frequency map.
    3. Second Pass: Iterate through the input string s again, this time from the beginning (index 0).
    4. For each character in this second pass, check its count in the frequency map.
    5. If a character's count is 1, it means it is the first non-repeating character in the string. Return its current index.
    6. If the second pass completes without finding any character with a count of 1, it means no unique character exists. In this case, return -1.
class Solution:
    def firstUniqChar(self, s: str) -> int:
        # Use a dictionary to store character counts
        char_counts = {}

        # First pass: Populate the frequency map
        for char in s:
            char_counts[char] = char_counts.get(char, 0) + 1

        # Second pass: Find the first unique character
        for i, char in enumerate(s):
            if char_counts[char] == 1:
                return i

        # If no unique character is found
        return -1