First Unique Character in a String
Understanding the Problem
We need to find the first character in the string that appears exactly once. "First" means the leftmost position, and "unique" means its count in the entire string is exactly one. If every character repeats, we return -1.
The challenge is the ordering. Deciding whether a character is unique requires the frequency of every character, which is global information about the whole string. But picking the answer requires the leftmost qualifying position, which is positional information. The two requirements pull in different directions, and that tension shapes the approaches below.
Key Constraints:
1 <= s.length <= 10^5→ With n up to 100,000, O(n^2) is borderline. O(n log n) and O(n) are safe. We should aim for O(n).s consists of only lowercase English letters→ Only 26 possible characters. A fixed-size array of length 26 is enough for counting, giving us O(1) space.
Approach 1: Brute Force
Intuition
For each character in the string, check whether it appears anywhere else. The first character with no duplicate is the answer.
This mirrors scanning a word by hand: take the first letter, look through the rest of the word for a match, and if none exists, that letter is the answer. Otherwise move to the next letter and repeat. Because we examine positions left to right, the first letter we find without a duplicate is automatically the leftmost one.
Algorithm
- Iterate through the string with index
ifrom 0 to n-1. - For each character at index
i, iterate through the entire string with indexj. - If
j != iands[j] == s[i], the character is not unique. Break and move to the nexti. - If the inner loop completes without finding a duplicate, return
i. - If no unique character is found after checking all positions, return
-1.
Example Walkthrough
Code
- Time Complexity: O(n^2). For each of the n characters, we potentially scan all n characters to check for duplicates.
- Space Complexity: O(1). No extra data structures beyond a boolean flag.
The brute force rescans the entire string for every character, recomputing duplicate information it has already seen. Counting each character's frequency once upfront turns every uniqueness check into an O(1) lookup.
Approach 2: Two-Pass Frequency Count
Intuition
Instead of repeatedly scanning for duplicates, count the frequency of every character in one pass, then make a second pass to find the first character with a count of exactly 1.
This splits the problem into two independent tasks: figure out which characters are unique, then find the leftmost one. The first task needs global information, so it scans the whole string. The second task needs positional information, so it scans left to right. Running them as two sequential passes keeps each one simple.
Since the string contains only lowercase English letters, a fixed-size array of 26 integers is enough to hold the counts. Array indexing avoids hash lookups, and the space stays constant regardless of input size.
The second pass visits positions in increasing index order and returns at the first one whose count is 1. Any earlier position must have had a count greater than 1, so it could not be the answer. The position returned is therefore the smallest index of any unique character.
Algorithm
- Create a frequency array of size 26 initialized to zeros.
- First pass: iterate through the string and count the frequency of each character.
- Second pass: iterate through the string again. For each character, check its frequency in the array. Return the index of the first character with frequency 1.
- If no character has frequency 1, return -1.
Example Walkthrough
Code
- Time Complexity: O(n). Two passes through the string, each doing O(1) work per character. The total is O(2n) = O(n).
- Space Complexity: O(1). The frequency array has a fixed size of 26, regardless of input length.
This is optimal for a fixed string given all at once. A common follow-up changes the setting: characters arrive one at a time as a stream, and after each arrival you must report the first unique character seen so far. The next approach handles that case and also solves the original problem in a single pass.
Approach 3: Streaming with a Queue
Intuition
The two-pass approach assumes the entire string is available before we start. A harder variant feeds characters one at a time and asks for the current first unique character after every arrival. We cannot make a second pass, because future characters have not arrived yet.
The fix is to keep a queue of candidate indices in arrival order, alongside the frequency counts. Each index enters the queue once, when its character first arrives. The front of the queue holds the oldest index that is still a candidate for "first unique." A candidate stops being valid the moment its character's count rises above 1, so before reading the answer we discard any front entries whose character now repeats. Whatever remains at the front is the first unique character. If the queue empties, no unique character exists.
This also solves the original fixed-string problem in a single pass: feed the characters in order, and the queue front after the last character is the final answer.
Algorithm
- Create a frequency array of size 26 and an empty queue of indices.
- Walk the string once. For each index
iwith characterc: incrementcount[c], and if this is the first timecis seen (count becomes 1), pushionto the queue. - After incrementing, drop indices from the front of the queue while the character at the front index has a count greater than 1. Those characters are no longer unique.
- After processing the whole string, the front of the queue is the index of the first unique character. Return it, or -1 if the queue is empty.
Example Walkthrough
Code
- Time Complexity: O(n). The string is scanned once. Each index is pushed onto the queue at most once and popped at most once, so the eviction loop does O(n) total work across the whole run, not O(n) per step.
- Space Complexity: O(1). The frequency array is fixed at 26. The queue only holds indices of characters that are currently candidates for "first unique," so it never contains more than 26 entries at a time.