387_First Unique Character in a String

[easy] [string, hash table]

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

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

Examples:

s = "leetcode"
return 0.

s = "loveleetcode",
return 2.

Solution 1: brute force

Idea:

• Loop over each character from left to right, count the number of its occurrence. If it only occur once, return the index.

Time Complexity: $O(n^2)$

Space Complexity: $O(1)$

def firstUniqChar(s):
    """
    :type s: str
    :rtype: int
    """

    for i in range(len(s)):
        c = s[i]
        if s.count(c) == 1: # can write count as a helper function if needed
            return i
    return -1

Solution 2: Use dictionary

Idea:

• Loop over each character from left to right.

• Store the character and its index in a dictionary if it's the first time it occur.

• If it occur more than once, store the character in another set.

• return the minimum index in the dictionary if exists.

Time Complexity: $O(n)$

Space Complexity: $O(n)$

def firstUniqChar(s):
    """
    :type s: str
    :rtype: int
    """

    dict1 = {} # for characters appear once
    dict2 = set() # for characters appear more than once
    for i in range(len(s)):
        c = s[i]
        if c not in dict1 and c not in dict2:
            dict1[c] = i
        elif c in dict1:
            del(dict1[c])
            dict2.add(c)
    return min(dict1.values()) if len(dict1) > 0 else -1