Problem 1143

Question statement:

Given a string s, find the first non-repeating character in it and return its index. If it does not exist, return -1.

Solution:

Main idea:

A counter is not going to work here, because it doesn’t store the location information – just the frequencies. The main idea is to scan through the string, adding a letter to a dictionary if we haven’t seen it before, with it’s value corresponding to its index. If the letter is already in the dictionary, then we delete that entry from the dictionary, and also store the letter in a “deleted” set, so we don’t add it back into the dictionary at a later point after deleting it.

Finally, after every letter has been scanned, the keys remaining in the dictionary corresond to unique letters that appear in the given string. At this point we simply return the minimum index stored in the dictionary.

Code:

def firstUniqChar(self, s: str) -> int:
    dic = defaultdict(int)
    deleted = set()
    for i in range(len(s)):
        if(s[i] not in deleted):
            if(s[i] in dic):
                deleted.add(s[i])
                del dic[s[i]]
            else:
                dic[s[i]] = i
    return -1 if not dic else min(dic.values())

Comments:

Time complexity: O(n)

At the time of submission, the above solution passes leetcode submission cases in 50ms, beats 99.55% of users. It uses 16.80MB of memory, beating 59.25% of users.