How do you solve First Unique Character in a String on LeetCode?

First Unique Character in a String (LeetCode #387) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(n) time complexity and O(n) space complexity. Key insight: Using a hash map allows for efficient counting of characters.

What is the brute force solution for First Unique Character in a String?

The brute force approach for First Unique Character in a String is Brute Force, with O(n²) time complexity and O(1) space complexity. The brute force approach checks each character in the string and counts how many times it appears. If a character appears only once, we return its index. This is straightforward but inefficient for larger strings. The optimal Optimal Solution approach improves this to O(n).

What algorithm or data structure is used to solve First Unique Character in a String?

First Unique Character in a String uses the following concepts: Hash Table, String, Queue, Counting. The recommended patterns to study are: Hash Map, Array.

What are the interview tips for First Unique Character in a String?

Always clarify the problem and constraints before diving into coding. Think about the time and space complexity of your solution. Practice explaining your thought process while coding.

What are common mistakes when solving First Unique Character in a String?

Not considering edge cases like empty strings or strings with all repeating characters. Overcomplicating the solution instead of using a simple counting approach.

#387

First Unique Character in a String

Easy

Hash TableStringQueueCountingHash MapArray

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n²)	O(n)
Space	O(1)	O(n)

💡

Intuition

Time O(n)Space O(n)

The optimal solution uses a hash map to count occurrences of each character in one pass, then checks for the first unique character in another pass. This is efficient and reduces the time complexity significantly.

⚙️

Algorithm

4 steps

1Step 1: Create a hash map to store character counts.
2Step 2: Loop through the string and populate the hash map with character counts.
3Step 3: Loop through the string again to find the first character with a count of 1.
4Step 4: Return the index of that character or -1 if none exists.

solution.py8 lines

1def firstUniqChar(s):
2    count = {}
3    for char in s:
4        count[char] = count.get(char, 0) + 1
5    for i in range(len(s)):
6        if count[s[i]] == 1:
7            return i
8    return -1

ℹ

Complexity note: The time complexity is O(n) because we traverse the string twice (once for counting and once for finding the unique character). Space complexity is O(n) due to the hash map storing character counts.

1Using a hash map allows for efficient counting of characters.
2Two passes through the string are often needed for counting and checking.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.