First Unique Character in a String
Last Updated: March 29, 2026
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 tricky part isn't finding unique characters. It's finding the first one. We need to know the frequency of every character before we can decide which ones are unique, but we also need to respect the original ordering to pick the leftmost unique one. This tension between needing global frequency information and positional ordering is what shapes the different approaches.
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
The most straightforward way: for each character in the string, check whether it appears anywhere else. The first character that doesn't have a duplicate is our answer.
This is what you'd naturally do if you were scanning a word on paper. Pick the first letter, scan the rest of the word for duplicates. If you find one, move to the second letter and repeat. The first letter with no duplicates wins.
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.
This brute force rescans the entire string for every character, recounting frequencies we've already seen. What if we counted each character's frequency once upfront, so checking uniqueness becomes O(1)?
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.
The key insight is separating the problem into two independent tasks: (1) figure out which characters are unique, and (2) find the leftmost one. The first task needs global information (scan the whole string), and the second needs positional information (scan left to right). Doing them as two sequential passes is clean and efficient.
Since the string only contains lowercase English letters, a fixed-size array of 26 integers is all we need. Array access is faster than hash map lookups, and the space is constant regardless of input size.
The first pass builds a complete picture of character frequencies. The second pass leverages that information: for each position in the original string, we check in O(1) whether that character is unique. Because we scan left to right, the first unique character we find is guaranteed to be the leftmost one.
This approach cleanly separates "what is unique" from "what comes first," solving each sub-problem optimally.
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 already optimal in Big-O terms. But instead of scanning the entire string a second time, what if we iterated over just the 26 letters and checked their first occurrence index?
Approach 3: Frequency Count with Alphabet Scan
Intuition
Here's a different angle. Instead of making a second pass over the string (which could be up to 10^5 characters), we can iterate over the 26 letters of the alphabet and, for each letter with frequency 1, record its first index in the string. The smallest such index is our answer.
In practice, the difference is negligible for n up to 10^5. But the thinking behind it matters: sometimes the set of possible values (26 letters) is much smaller than the input size (n characters), and iterating over the smaller set is a useful technique that applies to many problems.
Algorithm
- Create a frequency array of size 26 initialized to zeros.
- First pass: iterate through the string and count each character's frequency.
- Initialize a variable
resulttonto track the smallest index of a unique character. - For each letter from 'a' to 'z': if its frequency is exactly 1, find its first occurrence index in the string using
indexOf. Updateresultif this index is smaller. - If
resultis stilln(unchanged), return -1. Otherwise, returnresult.
Example Walkthrough
Code
- Time Complexity: O(n). The first pass counts frequencies in O(n). The second pass iterates over 26 letters, calling
indexOffor each unique one. Each call is O(n) worst case, but at most 26 calls, so O(26n) = O(n). - Space Complexity: O(1). The frequency array is a fixed size of 26. Constant space.