First Unique Character in a String
EasyPrompt
Approaches
3 approaches with complexity analysis and trade-offs.
This is the most straightforward but least efficient approach. It involves iterating through each character of the string and, for each character, iterating through the string again to see if any other character matches it. If no match is found after checking the entire string, we've found our first unique character.
Algorithm
- Iterate through the string with an outer loop from
i = 0ton-1, wherenis the length of the string. - For each character
s[i], assume it is unique. - Start an inner loop from
j = 0ton-1to check for duplicates. - If a character
s[j]is found such thats[i] == s[j]andi != j, then the characters[i]is not unique. Break the inner loop. - If the inner loop completes without finding any duplicates, it means
s[i]is the first unique character. Return its indexi. - If the outer loop completes and no unique character is found, return -1.
Walkthrough
The brute-force method uses two nested loops. The outer loop picks a character, and the inner loop checks if that character appears anywhere else in the string. A boolean flag, isUnique, can be used to track whether a duplicate has been found for the character selected by the outer loop. If the inner loop finishes and the flag remains true, we have found the first unique character and can return its index. If the outer loop finishes without finding any such character, it means no unique characters exist, and we return -1.
class Solution { public int firstUniqChar(String s) { int n = s.length(); for (int i = 0; i < n; i++) { boolean isUnique = true; for (int j = 0; j < n; j++) { if (i != j && s.charAt(i) == s.charAt(j)) { isUnique = false; break; } } if (isUnique) { return i; } } return -1; }}Complexity
Time
O(N^2), where N is the length of the string. For each of the N characters, we iterate through the string again, which takes O(N) time.
Space
O(1), as no extra data structures are used that scale with the input size.
Trade-offs
Pros
Simple to understand and implement.
Uses constant extra space, O(1).
Cons
Highly inefficient with a time complexity of O(N^2).
Will likely result in a 'Time Limit Exceeded' error on platforms like LeetCode for larger inputs (e.g., N > 10^4).
This approach leverages built-in string searching functions. A character is unique if and only if its first index in the string is the same as its last index. We can iterate through the 26 lowercase English letters, and for each letter, we find its first and last index in the input string. If they are the same, the character is unique. We keep track of the minimum index found among all unique characters.
Algorithm
- Initialize a variable
minIndexto a very large value (or -1 as a flag). - Iterate through all possible characters in the alphabet (from 'a' to 'z').
- For each character
c, find its first occurrence in the string usings.indexOf(c). - If the character
cexists in the string (i.e.,indexOfdoes not return -1), check if its last occurrence is at the same position usings.lastIndexOf(c). - If
s.indexOf(c) == s.lastIndexOf(c), the character is unique. We then updateminIndexwith the smaller value between the currentminIndexand this character's index. - After checking all 26 characters, if
minIndexis still the initial large value, it means no unique character was found, so return -1. Otherwise, returnminIndex.
Walkthrough
Instead of iterating through the string itself, we iterate through the constant-size alphabet ('a' through 'z'). For each character, we use s.indexOf(char) and s.lastIndexOf(char). If these two methods return the same index, it confirms the character appears exactly once. We want the first such unique character, so we maintain a variable, minIndex, to store the minimum index seen so far among all unique characters. This ensures we find the one that appears earliest in the string.
class Solution { public int firstUniqChar(String s) { int minIndex = Integer.MAX_VALUE; for (char c = 'a'; c <= 'z'; c++) { int index = s.indexOf(c); // Check if character exists and is unique if (index != -1 && index == s.lastIndexOf(c)) { minIndex = Math.min(minIndex, index); } } // If minIndex was never updated, no unique character was found return minIndex == Integer.MAX_VALUE ? -1 : minIndex; }}Complexity
Time
O(N). The outer loop runs a constant number of times (26). Inside the loop, `indexOf` and `lastIndexOf` each take O(N) time in the worst case. Thus, the total complexity is O(26 * N), which simplifies to O(N).
Space
O(1), as we only use a few variables to store the indices, regardless of the input string size.
Trade-offs
Pros
Linear time complexity O(N).
Constant space complexity O(1).
Code is often concise and easy to read.
Cons
Although the asymptotic complexity is O(N), it can be slower in practice than the hash map approach because it may perform many passes over the string (up to 52 scans for
indexOfandlastIndexOf).
This is the most common and efficient approach. It solves the problem in two linear passes. The first pass is to build a frequency count of all characters in the string. The second pass is to iterate through the string again and return the index of the first character that has a frequency of 1.
Algorithm
- First Pass (Frequency Counting): Create a frequency map (or an integer array of size 26 for lowercase letters). Iterate through the input string
sfrom beginning to end. For each character, increment its corresponding count in the frequency map. - Second Pass (Find First Unique): Iterate through the string
sa second time, again from beginning to end. - For each character
s[i], look up its count in the frequency map. - If the count is 1, this is the first unique character we've encountered. Return its index
i. - If the second loop completes without finding any character with a frequency of 1, it means no unique characters exist. Return -1.
Walkthrough
We can use a data structure to store the counts of each character. Since the problem states the string only contains lowercase English letters, a simple integer array of size 26 is a highly efficient choice for a frequency map. counts[c - 'a'] will store the frequency of character c.
First, we iterate through the string to populate this counts array. Then, we iterate through the string a second time. For each character, we check its count in the array. The first time we find a character whose count is 1, we've found our answer and can immediately return its index. If we finish the second loop, it means no character had a count of 1, so we return -1.
class Solution { public int firstUniqChar(String s) { int[] counts = new int[26]; int n = s.length(); // First pass: build frequency map for (int i = 0; i < n; i++) { char c = s.charAt(i); counts[c - 'a']++; } // Second pass: find first unique character for (int i = 0; i < n; i++) { char c = s.charAt(i); if (counts[c - 'a'] == 1) { return i; } } return -1; }}Complexity
Time
O(N), where N is the length of the string. We make two passes through the string, one to count frequencies (O(N)) and one to find the unique character (O(N)). The total time is O(N) + O(N) = O(N).
Space
O(1), because the size of the frequency array (26) is constant and does not depend on the length of the input string.
Trade-offs
Pros
Optimal time complexity of O(N).
Generally faster in practice than the
indexOfmethod due to better data locality and fewer total operations.A standard and widely applicable pattern for frequency-related problems.
Cons
Requires two separate passes over the input string.
Uses extra space for the frequency map, although it's constant space (O(1)) for a fixed alphabet.
Solutions
Solution
class Solution {public int firstUniqChar(String s) { int[] cnt = new int[26]; int n = s.length(); for (int i = 0; i < n; ++i) { ++cnt[s.charAt(i) - 'a']; } for (int i = 0; i < n; ++i) { if (cnt[s.charAt(i) - 'a'] == 1) { return i; } } return -1; }}/** * @param {string} s * @return {number} */ var firstUniqChar = function (s) { const cnt = new Array(26).fill(0); for (const c of s) { ++cnt[c.charCodeAt() - " a ".charCodeAt()]; } for (let i = 0; i < s.length; ++i) { if (cnt[s[i].charCodeAt() - " a ".charCodeAt()] === 1) { return i; } } return -1;};class Solution {public: int firstUniqChar(string s) { int cnt[26]{}; for (char &c : s) { ++cnt[c - 'a']; } int n = s.size(); for (int i = 0; i < n; ++i) { if (cnt[s[i] - 'a'] == 1) { return i; } } return -1; }};class Solution: def firstUniqChar(self, s: str) -> int: cnt = Counter(s) for i, c in enumerate(s): if cnt[c] == 1: return i return - 1Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.