First Unique Character in a String
Return the index of the first non-repeating character, or -1.
3 min read
hash-map counting strings
Problem#
Given a string s of lowercase letters, return the index of the first character that appears exactly once, or -1.
Examples#
"leetcode"→0."loveleetcode"→2."aabb"→-1.
Constraints#
1 <= s.length <= 10^5.
Hints#
Hint
Count first, scan second — first index where count is 1 is the answer.
Approach#
Two passes. First pass tally counts; second pass returns the first index with count 1.
Solution#
class Solution {public: int firstUniqChar(string s) { int cnt[26] = {0}; for (char c : s) ++cnt[c - 'a']; for (int i = 0; i < (int)s.size(); ++i) if (cnt[s[i] - 'a'] == 1) return i; return -1; }};func firstUniqChar(s string) int { var cnt [26]int for i := 0; i < len(s); i++ { cnt[s[i]-'a']++ } for i := 0; i < len(s); i++ { if cnt[s[i]-'a'] == 1 { return i } } return -1}from collections import Counter
class Solution: def firstUniqChar(self, s: str) -> int: cnt = Counter(s) for i, c in enumerate(s): if cnt[c] == 1: return i return -1var firstUniqChar = function(s) { const cnt = new Array(26).fill(0); const A = 'a'.charCodeAt(0); for (let i = 0; i < s.length; i++) cnt[s.charCodeAt(i) - A]++; for (let i = 0; i < s.length; i++) { if (cnt[s.charCodeAt(i) - A] === 1) return i; } return -1;};class Solution { public int firstUniqChar(String s) { int[] cnt = new int[26]; for (int i = 0; i < s.length(); i++) cnt[s.charAt(i) - 'a']++; for (int i = 0; i < s.length(); i++) { if (cnt[s.charAt(i) - 'a'] == 1) return i; } return -1; }}function firstUniqChar(s: string): number { const cnt: number[] = new Array(26).fill(0); const A = 'a'.charCodeAt(0); for (let i = 0; i < s.length; i++) cnt[s.charCodeAt(i) - A]++; for (let i = 0; i < s.length; i++) { if (cnt[s.charCodeAt(i) - A] === 1) return i; } return -1;}Editorial#
Two passes are necessary because uniqueness is only known after seeing the whole string. Using int[26] keeps memory tight; the scan is O(N). A streaming version (one pass) is possible with a doubly-linked list of indices but complicates the code without complexity gains for this problem size.
Complexity#
- Time: O(N).
- Space: O(1).
Concept revision#
Related#