Leetcode: First unique character in string
Given a string s
, find the first non-repeating character in it and return its index. If it does not exist, return -1
. An example is the word leetcode
where the l
only appears once, therefore returning 0
as result.
The obvious, but very slow, solution is to iterate over the string and then for ever character, check the whole string if the character appears again. This has a time complexity of O(n^2)
.
A better solution is to write all characters in a map and count the number of occurrences. This way, we can iterate again and simply look at the counter in the map. This yields a time complexity of O(2n)
.
class Solution:
def firstUniqChar(self, s: str) -> int:
c = {}
for char in s:
if char not in c:
c[char] = 0
c[char] += 1
for idx in range(len(s)):
if c[s[idx]] == 1:
return idx
return -1
if __name__ == '__main__':
s = Solution().firstUniqChar
print(s('leetcode'), 0)
print(s('loveleetcode'), 2)
print(s('aabb'), -1)