Friedrich Ewald My Personal Website

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)

About the author

is an experienced Software Engineer with a Master's degree in Computer Science. He started this website in late 2015, mostly as a digital business card. He is interested in Go, Python, Ruby, SQL- and NoSQL-databases, machine learning and AI and is experienced in building scalable, distributed systems and micro-services at multiple larger and smaller companies.