Description
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 <= 105s consists of only lowercase English letters.
Solutions
Solution 1: Counting
We use a hash table or an array of length 26 cnt to store the frequency of each character. Then, we traverse each character s[i] from the beginning. If cnt[s[i]] is 1, we return i.
If no such character is found after the traversal, we return -1.
The time complexity is O(n), where n is the length of the string. The space complexity is O(|Σ|), where Σ is the character set. In this problem, the character set consists of lowercase letters, so |Σ|=26.
PythonJavaC++GoTypeScriptJavaScriptPHP
class Solution:
def firstUniqChar(self, s: str) -> int:
cnt = Counter(s)
for i, c in enumerate(s):
if cnt[c] == 1:
return i
return -1(code-box)
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;
}
}(code-box)
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;
}
};(code-box)
func firstUniqChar(s string) int {
cnt := [26]int{}
for _, c := range s {
cnt[c-'a']++
}
for i, c := range s {
if cnt[c-'a'] == 1 {
return i
}
}
return -1
}(code-box)
function firstUniqChar(s: string): number {
const cnt = new Map<string, number>();
for (const c of s) {
cnt.set(c, (cnt.get(c) || 0) + 1);
}
for (let i = 0; i < s.length; ++i) {
if (cnt.get(s[i]) === 1) {
return i;
}
}
return -1;
}(code-box)
/**
* @param {string} s
* @return {number}
*/
var firstUniqChar = function (s) {
const cnt = new Map();
for (const c of s) {
cnt.set(c, (cnt.get(c) || 0) + 1);
}
for (let i = 0; i < s.length; ++i) {
if (cnt.get(s[i]) === 1) {
return i;
}
}
return -1;
};(code-box)
class Solution {
/**
* @param String $s
* @return Integer
*/
function firstUniqChar($s) {
for ($i = 0; $i < strlen($s); $i++) {
$hashtable[$s[$i]]++;
}
for ($i = 0; $i < strlen($s); $i++) {
if ($hashtable[$s[$i]] == 1) {
return $i;
}
}
return -1;
}
}(code-box)
