387. First Unique Character in a String - Explanation

Problem Link

Description

You are 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 = "neetcodeislove"

Output: 0

Explanation: The character 'n' at index 0 is the first character that does not occur at any other index.

Example 2:

Input: s = "neetcodeneet"

Output: 4

Example 3:

Input: s = "baab"

Output: -1

Constraints:

• 1 <= s.length <= 1,00,000
• s consists of only lowercase English letters.

Company Tags

Please upgrade to NeetCode Pro to view company tags.

1. Brute Force

Intuition

For each character in the string, we check if it appears anywhere else. If a character has no duplicate, it is unique. The first such character we find (going left to right) is our answer.

Algorithm

1. Iterate through each index i in the string.
2. For each character at i, compare it with every other character at index j.
3. If a match is found (where i != j), mark it as non-unique and break.
4. If no match is found after checking all positions, return i.
5. If no unique character exists, return -1.

class Solution:
    def firstUniqChar(self, s: str) -> int:
        for i in range(len(s)):
            flag = True
            for j in range(len(s)):
                if i == j:
                    continue
                if s[i] == s[j]:
                    flag = False
                    break
            if flag:
                return i
        return -1

Time & Space Complexity

• Time complexity: $O(n ^ 2)$
• Space complexity: $O(1)$

---

2. Hash Map

Intuition

Instead of checking every pair of characters, we can count the frequency of each character in a single pass. Then, in a second pass, we find the first character whose count is exactly 1. This trades space for time.

Algorithm

1. Create a hash map to store the count of each character.
2. First pass: iterate through the string and increment the count for each character.
3. Second pass: iterate through the string again and return the index of the first character with count equal to 1.
4. If no unique character is found, return -1.

class Solution:
    def firstUniqChar(self, s: str) -> int:
        count = defaultdict(int)
        for c in s:
            count[c] += 1

        for i, c in enumerate(s):
            if count[c] == 1:
                return i
        return -1

Time & Space Complexity

• Time complexity: $O(n)$
• Space complexity: $O(1)$ since we have at most $26$ different characters.

---

3. Hash Map (Optimal)

Intuition

We can optimize the second pass by iterating over the hash map instead of the string. For each character, we store its first occurrence index. If the character appears again, we mark it as non-unique by setting its index to n (string length). Finally, we find the minimum index among all unique characters.

Algorithm

1. Create a hash map where each character maps to its first occurrence index.
2. Iterate through the string:
   • If the character is not in the map, store its index.
   • If it already exists, mark it as non-unique by setting the value to n.
3. Find the minimum value in the hash map.
4. Return the minimum index if it's less than n, otherwise return -1.

class Solution:
    def firstUniqChar(self, s: str) -> int:
        n = len(s)
        count = defaultdict(int)
        for i, c in enumerate(s):
            if c not in count:
                count[c] = i
            else:
                count[c] = n

        res = n
        for c in count:
            res = min(res, count[c])

        return -1 if res == n else res

Time & Space Complexity

• Time complexity: $O(n)$
• Space complexity: $O(1)$ since we have at most $26$ different characters.

---

4. Iteration

Intuition

Since the string contains only lowercase letters, we can iterate through all 26 characters and find the first occurrence of each. If a character's first and last occurrence are the same index, it appears exactly once. We track the minimum such index across all characters.

Algorithm

1. Initialize res to the string length n.
2. For each character from 'a' to 'z':
   • Find its first occurrence index using indexOf (or equivalent).
   • Find its last occurrence index using lastIndexOf.
   • If both indices are equal and the character exists, update res with the minimum.
3. Return res if it's less than n, otherwise return -1.

class Solution:
    def firstUniqChar(self, s: str) -> int:
        res = n = len(s)
        for ch in range(ord('a'), ord('z') + 1):
            index = s.find(chr(ch))
            if index != -1 and s.rfind(chr(ch)) == index:
                res = min(res, index)

        return -1 if res == n else res

Time & Space Complexity

• Time complexity: $O(26 * n)$ since we have at most $26$ different characters.
• Space complexity: $O(1)$