First Unique Character in a String

Difficulty: Easy | Acceptance: 65.40% | Paid: No Topics: Hash Table, String, Queue, Counting

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

• Examples
• Constraints
• Brute Force
• Hash Map - Two Pass
• Array Counting
• Queue

Examples

Example 1

Input: s = "leetcode"
Output: 0

Example 2

Input: s = "loveleetcode"
Output: 2

Example 3

Input: s = "aabb"
Output: -1

Constraints

1 <= s.length <= 10⁵
s consists of only lowercase English letters.

Brute Force

Intuition For each character in the string, check if it appears anywhere else in the string. The first character that doesn’t repeat is our answer.

Steps

• Iterate through each character in the string
• For each character, scan the entire string to check for duplicates
• Return the index of the first character with no duplicates
• Return -1 if no unique character exists

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

Complexity

• Time: O(n²)
• Space: O(1)
• Notes: Simple but inefficient for large strings due to nested loops.

Hash Map - Two Pass

Intuition First pass counts the frequency of each character using a hash map. Second pass finds the first character with frequency 1.

Steps

• Create a hash map to store character frequencies
• First pass: iterate through string and count each character
• Second pass: iterate through string again and return index of first character with count 1
• Return -1 if no unique character found

class Solution:
    def firstUniqChar(self, s: str) -> int:
        count = {}
        for c in s:
            count[c] = count.get(c, 0) + 1
        for i, c in enumerate(s):
            if count[c] == 1:
                return i
        return -1

Complexity

• Time: O(n)
• Space: O(1) - at most 26 unique characters
• Notes: Optimal time complexity with minimal space overhead.

Array Counting

Intuition Since the string contains only lowercase English letters, we can use a fixed-size array of 26 elements instead of a hash map for better performance.

Steps

• Create an integer array of size 26 initialized to 0
• First pass: count each character by mapping ‘a’ to index 0, ‘b’ to index 1, etc.
• Second pass: find the first character with count 1 and return its index
• Return -1 if no unique character exists

class Solution:
    def firstUniqChar(self, s: str) -> int:
        count = [0] * 26
        for c in s:
            count[ord(c) - ord('a')] += 1
        for i, c in enumerate(s):
            if count[ord(c) - ord('a')] == 1:
                return i
        return -1

Complexity

• Time: O(n)
• Space: O(1) - fixed array of 26 integers
• Notes: Most efficient approach due to array cache locality and no hashing overhead.

Queue

Intuition Use a queue to maintain characters in order of appearance, removing characters from the front when they are found to be duplicates.

Steps

• Create a hash map to track character frequencies and a queue to store (character, index) pairs
• For each character in the string, increment its count and add it to the queue
• Remove characters from the front of the queue if their count exceeds 1
• After processing all characters, the front of the queue contains the first unique character
• Return its index or -1 if queue is empty

from collections import deque

class Solution:
    def firstUniqChar(self, s: str) -> int:
        count = {}
        queue = deque()
        for i, c in enumerate(s):
            count[c] = count.get(c, 0) + 1
            queue.append((c, i))
            while queue and count[queue[0][0]] > 1:
                queue.popleft()
        return queue[0][1] if queue else -1

Complexity

• Time: O(n)
• Space: O(1) - at most 26 unique characters in queue
• Notes: Useful for streaming scenarios where we need to find first unique character as we process input.