Given a string s, find the first non-repeating character in it and return its index. If it does not exist, return -1.
Example 1:
Input: s = "leetcode"
Output: 0
Explanation:
The character 'l' at index 0 is the first character that does not occur at any other index.
Example 2:
Input: s = "loveleetcode"
Output: 2
Example 3:
Input: s = "aabb"
Output: -1
Constraints:
- 1 <= s.length <= 105
- s consists of only lowercase English letters.
My Solution
We can do one pass of the string to find the counts of each character. Then we do another pass of the string. We return the index of the first character for which the count is 1. If we traverse the string and don’t find any character with count of 1, we return -1.
Time complexity is O(n) since we do two passes through the array. Space complexity is O(1) because our counts array only has a total of 26 elements, which is constant.
class Solution {
public int firstUniqChar(String s) {
int[] counts = new int[26];
int n = s.length();
for (int i = 0; i < n; i++) {
char c = s.charAt(i);
counts[c-'a']++;
}
for (int i = 0; i < n; i++) {
char c = s.charAt(i);
if (counts[c-'a'] == 1) {
return i;
}
}
return -1;
}
}