LeetCode #387: First Unique Character in a String

Description:

Given a string, find the first non-repeating character in it and return it's index. If it doesn't exist, return -1.

Examples:

s = "leetcode"
return 0.

s = "loveleetcode",
return 2.

Note: You may assume the string contain only lowercase letters.

Solution:

• Method 1: first traverse the string to get a hash table recording the counts of each character, then traverse the string again to get the first unique character.

  • Time complexity: O(N) for best case; O(2N) for worst case
  • Space complexity: O(26)

• Method 2: first traverse the string to get a hash table recording the list of indices for each character, then traverse the hash table to get the first unique character.

  • Time complexity: O(N+26)
  • Space complexity: O(N)

• Method 3: first traverse the string backward to get two hash tables, one for counts and the other for the first index, then traverse the hash tables to get the location of the first unique character

  • Time complexity: O(N+26)
  • Space complexity: O(26*2)

class Solution:
    def firstUniqChar(self, s: str) -> int:
        method = 3

        if method == 1:
            from collections import defaultdict        
            d = defaultdict(int, {})
            for x in s: 
                d[x] += 1
            i = 0
            for x in s:
                if d[x] == 1: return i
                i += 1
            return -1

        if method == 2:
            from collections import defaultdict        
            d = defaultdict(list, {})
            for i in range(len(s)): 
                d[s[i]].append(i)

            for x in d.keys():
                if len(d[x]) == 1: return d[x][0]
            return -1

        if method == 3:
            from collections import defaultdict, OrderedDict      
            d = OrderedDict()
            c = defaultdict(int, {})
            for i in range(len(s))[::-1]:
                d[s[i]] = i
                c[s[i]] += 1

            for x in list(d.keys())[::-1]:
                if c[x] == 1: return d[x]
            return -1