NUHMAN.com

📘 Problem Statement

Given a string s, find the first unique character in the string and return its index. If it doesn't exist, return -1.

Note:

• You must implement an algorithm that runs in O(n) time complexity where n is the length of the string.

📚 Example:

python

Input:
s = "leetcode"
Output:
0

Input:
s = "loveleetcode"
Output:
2

Input:
s = "aabb"
Output:
-1

🧠 Key Insight

To solve this problem efficiently, we can use a hash map (dictionary) to keep track of the frequency of each character in the string. After the frequencies are counted, we can traverse the string again to find the first character that appears only once.

💡 Approach

1. Counting Character Frequencies:

• We first traverse the string and count the frequency of each character using a hash map (dictionary).

1. Finding the First Unique Character:

• After counting the frequencies, we traverse the string again and check for the first character with a frequency of 1.

1. Edge Case:

• If no character has a frequency of 1, return -1.

🐍 Python Code

python

class Solution:
    def firstUniqChar(self, s: str) -> int:
        # Step 1: Create a frequency map
        freq_map = {}
        
        # Step 2: Count the frequency of each character
        for char in s:
            if char in freq_map:
                freq_map[char] += 1
            else:
                freq_map[char] = 1
        
        # Step 3: Find the first character with frequency 1
        for index, char in enumerate(s):
            if freq_map[char] == 1:
                return index
        
        # If no unique character is found, return -1
        return -1

🔍 Step-by-Step Explanation

1. Count the Frequency of Each Character

python

freq_map = {}
for char in s:
    if char in freq_map:
        freq_map[char] += 1
    else:
        freq_map[char] = 1

• We initialize an empty dictionary called freq_map.
• Then, we iterate through each character char in the string s. For each character, we check if it is already in the dictionary:
• If it is, we increment its count.
• If it is not, we add it to the dictionary with an initial count of 1.

2. Find the First Unique Character

python

for index, char in enumerate(s):
    if freq_map[char] == 1:
        return index

• After counting the frequencies of all characters, we iterate through the string s again, using enumerate to get both the index and character.
• We check if the frequency of the current character is 1 (indicating it is unique).
• If it is unique, we return the index of that character.

3. Handle the Case of No Unique Character

python

return -1

• If we have finished iterating through the string and have not found any unique character, we return -1.

💡 Example Walkthrough

Example 1:

python

Input:
s = "leetcode"
Output:
0

1. Count Character Frequencies:

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

1. Find the First Unique Character:

• The first unique character is 'l' at index 0.

1. Return Index:

• The function returns 0.

Example 2:

python

Input:
s = "loveleetcode"
Output:
2

1. Count Character Frequencies:

• {'l': 2, 'o': 2, 'v': 1, 'e': 4, 't': 1, 'c': 1, 'd': 1}

1. Find the First Unique Character:

• The first unique character is 'v' at index 2.

1. Return Index:

• The function returns 2.

Example 3:

python

Input:
s = "aabb"
Output:
-1

1. Count Character Frequencies:

• {'a': 2, 'b': 2}

1. Find the First Unique Character:

• There is no unique character.

1. Return -1:

• The function returns -1.

⏱️ Time & Space Complexity

MetricComplexityTime ComplexityO(n)Space ComplexityO(n)

• Time Complexity:
• We traverse the string twice: once to build the frequency map and once to find the first unique character. Thus, the time complexity is O(n), where n is the length of the string.
• Space Complexity:
• We use a dictionary to store the frequency of characters, so the space complexity is O(n) in the worst case (when all characters are unique).

🧵 Final Thoughts

LeetCode 387 is a classic problem that helps practice efficient string traversal techniques. By utilizing a hash map to count character frequencies and performing a second traversal to find the first unique character, this approach ensures an optimal solution with O(n) time complexity.

This problem can be expanded into variations that might involve different types of data structures or require further optimizations, but the solution presented here is both simple and efficient for the problem constraints.