Problem
Given a string s, return the index of the first character that appears exactly once. If no such character exists, return -1.Example(s)
Consider the following example(s) to understand the expected input and output.Input
s = "backtoback" Output
4 Solution
This solution uses a HashMap to track each character. During the first pass, a character is stored with its index when seen for the first time.If it appears again, its value is updated to -1 to indicate that it is no longer unique.
In the second pass, the string is traversed again to find the first character whose stored value is not -1. Since the string is scanned in its original order, the first unique character is returned immediately.
public int firstUniqChar(String s) {
Map<Character, Integer> map = new HashMap<>();
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
if (map.containsKey(c)) {
map.put(c, -1);
} else {
map.put(c, i);
}
}
for (char c : s.toCharArray()) {
if (map.get(c) != -1) {
return map.get(c);
}
}
return -1;
}
It avoids object creation and hashing overhead while still requiring only two linear passes.
public int firstUniqChar(String s) {
int[] chars = new int[26];
for (char c : s.toCharArray()) {
chars[c - 'a']++;
}
for (int i = 0; i < s.length(); i++) {
if (chars[s.charAt(i) - 'a'] == 1) {
return i;
}
}
return -1;
}
Complexity
Both implementations scan the string twice, resulting in a linear time complexity ofO(n). The HashMap solution requires
O(n) extra space in the worst case, whereas the array-based solution uses a fixed-size array and therefore requires only O(1) extra space.