First Unique Character In A String - Leetcode Solution

Problem Statement:

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

Approach:

We can solve this problem by using a hashmap to keep track of the count of each character in the string. Then, we can iterate over the string again and return the index of the first character whose count is one.

Algorithm:

1. Initialize a hashmap to keep track of the count of characters in the string.
2. Iterate over the string s and increment the count for each character in the hashmap.
3. Iterate over the string again and return the index of the first character whose count is one.
4. If no such character is found, return -1.

Code:

Python:

class Solution:
    def firstUniqChar(self, s: str) -> int:
        # Step 1: Initialize a hashmap to keep track of the count of characters in the string.
        char_count = {}
        
        # Step 2: Iterate over the string s and increment the count for each character in the hashmap.
        for char in s:
            if char in char_count:
                char_count[char] += 1
            else:
                char_count[char] = 1
        
        # Step 3: Iterate over the string again and return the index of the first character whose count is one.
        for i, char in enumerate(s):
            if char_count[char] == 1:
                return i
        
        # Step 4: If no such character is found, return -1.
        return -1

Complexity Analysis:

• Time Complexity: O(n), where n is the length of the string s. We iterate over the string twice, once to build the hashmap and once to find the first non-repeating character. The time complexity of building the hashmap is O(n) and finding the first non-repeating character is also O(n).
• Space Complexity: O(n), where n is the length of the string s. We are using a hashmap to store the count of characters in the string, which can have a maximum of n distinct characters. Therefore, the space complexity is O(n).

1