Problem
Given a string s, find the index of the first character that appears only once. Return -1 if none exists.
Example
Input: "leetcode"
Output: 0Input: "loveleetcode"
Output: 2Solution
Two passes: first count all characters, then find the first one with count 1.
def first_uniq_char(s):
counts = {}
for ch in s:
counts[ch] = counts.get(ch, 0) + 1
for i, ch in enumerate(s):
if counts[ch] == 1:
return i
return -1function firstUniqChar(s) {
const counts = {};
for (const ch of s) counts[ch] = (counts[ch] || 0) + 1;
for (let i = 0; i < s.length; i++) {
if (counts[s[i]] === 1) return i;
}
return -1;
}int firstUniqChar(string s) {
int counts[26] = {0};
for (char ch : s) counts[ch - 'a']++;
for (int i = 0; i < s.size(); i++) {
if (counts[s[i] - 'a'] == 1) return i;
}
return -1;
}public int firstUniqChar(String s) {
int[] counts = new int[26];
for (char ch : s.toCharArray()) counts[ch - 'a']++;
for (int i = 0; i < s.length(); i++) {
if (counts[s.charAt(i) - 'a'] == 1) return i;
}
return -1;
}Complexity
- Time: O(n)
- Space: O(1) for fixed alphabet
Explanation
Two passes through the string. First counts frequencies, second finds the first character with frequency 1.
Comments
Join the discussion. Got a question, found an issue, or want to share your experience?