Leetcode 387 (Python3)

Prompt:

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

s = "leetcode"
return 0.

s = "loveleetcode"
return 2.

Solution

def firstUniqChar(s: str):
    count = {}
    for index in range(len(s)):
        current_char = s[index]
        if current_char not in count:
            count[s[index]] = (1, index)
        else:
            count[s[index]] = (count[s[index]][0] + 1, index)
    for character, occurrence_counter in count.items():
        if occurrence_counter[0] == 1:
            return occurrence_counter[1]
    return -1

# Test Case
def test(actual, expected):
    if actual == expected:
        print("SUCCESS")
    else:
        print("FAILURE")
        print("Actual", actual)
        print("Expected", expected)

test(firstUniqChar("leetcode"), 0) # SUCCESS
test(firstUniqChar("loveleetcode"), 2) # SUCCESS
test(firstUniqChar(""), -1) # SUCCESS

Explained

  1. Builds a dictionary by iteratinng through given string. Hashes the occurrence as well as index position.
  2. Iterates through dictionary and returns first hit of unique character, where occurrence value is 1.

    Other points:

  • Dictionary is ordered in added order. The first hit is the earliest occurrence and can be returned as the solution, as stated in 2.
  • Corner case of empty string "" returns -1.

    Topics:

  • Linear Search
  • Hash map (python dict)
Written on December 7, 2020