Jan Meppe

Machine learning engineer in love with building digital products.

4 minute read

In this blogpost I tackle Leetcode problem 378 on finding the first unique character in a string.

The problem

The problem is defined as follows:

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

With some example input and output

s = "leetcode"
return 0.

s = "loveleetcode",
return 2.

General strategy

I first tried to go with a brute force strategy, but intuitively already felt the need for a hashmap type of solution.

I found out that getting the brute force algorithm to work was too much effort and the hashmap solution that I intuited turned out to be very quick and elegant.

Brute force solution

In pseudocode:

  • Start at the beginning and take the character
  • Loop for every other character in the array and check if it is the same
    • If character is not the same, it is unique, return index
    • If character is the same, go to next

This was my first solution

def firstUniqChar(: str) -> int:     
    for i in range(len(s)-1):
        unique = True
        for j in range(i+1, len(s)):
          # loop through all other characters
          # if character is no match for all of them we found a unique one
          # if character does match, not unique, continue with next
          # print(f"Comparing {s[i]} with {s[j]} ")
          if s[i] == s[j]:
            unique = False
        if unique == True:
          return i
      # No unique chars found
    return -1

This failed on a test case with a single character input, say z which shouldve returned 0 of course. We can fix this with a simple rule:

def firstUniqChar(s: str) -> int:
    if len(s)==1: 
        return 0
    for i in range(len(s)-1):
        unique = True
        for j in range(i+1, len(s)):
          # loop through all other characters
          # if character is no match for all of them we found a unique one
          # if character does match, not unique, continue with next
          print(f"Comparing {s[i]} with {s[j]} ")
          if s[i] == s[j]:
            unique = False

        if unique == True:
          return i
      # No unique chars found
    return -1

This fails on another test case aadadaad, this is because it does not keep track that the a is already seen. We make another list that we call seen and keep track of the things we’ve seen already. Darned, this also fails on another test case:

def firstUniqChar(s: str) -> int:
    seen = []
    if len(s)==1: 
        return 0
    for i in range(len(s)-1):
        unique = True
        for j in range(i+1, len(s)):
          # loop through all other characters
          # if character is no match for all of them we found a unique one
          # if character does match, not unique, continue with next
          print(f"Comparing {s[i]} with {s[j]} ")
          if s[i] == s[j] or s[i] in seen:
            unique = False
        seen.append(s[i])
        if unique == True:
          return i
      # No unique chars found
    return -1

This one fails on the test case where the unique character is the last one.

At this point I was almost willing to give up the brute force solution. It turned out to be significantly more difficult than I expected. I decided to throw my whole solution out and started with a blank slate.

def firstUniqChar(s: str) -> int:
  # Edge case s is single character
  if len(s) == 1: 
    return 0
  seen = []
  for i in range(len(s)):
    unique = True
    # Edge case where last char is unique one
    if i==len(s)-1:
      if s[i] in seen:
        return -1
      if s[i] not in seen: 
        return i
    for j in range(i+1, len(s)):
      # print(i, j, s[i])
      if s[i] == s[j] or s[i] in seen: 
        unique = False
    seen.append(s[i])
    if unique == True: 
      return i
  # No unique chars found
  return -1

I built this monstrosity and then… it timed out.

It was too slow.

I already realised that my solution would run in quadratic time but didn’t expect it to actually timeout. Oh well, on to the hashmap solution then.

Hashmap solution

To solve this problem we use a so-called hashmap.

The basic idea is to go through the whole string once and to keep track (in a hashmap/dictionary) the things we’ve seen already.

def firstUniqChar(s: str) -> int:
  seen = []
  saved = {}
  i = 0
  for c in s:
    if c in seen: 
      saved.pop(c, None)
    else:
      saved[c] = i
    seen.append(c)
    i = i+1
  # Return smallest index or return -1 if no unique
  if saved: 
    return min(saved.items(), key=lambda x: x[1])[1]
  else: 
    return -1

In pseudocode:

  • Keep track a list of seen characters seen = ['a', 'b', ...]
  • Keep track of uniques saved = {'a': 1, ...}
  • Loop through string once:
    • If we see a duplicate, remove from saved
    • If we see a new character, save it in saved
    • Update seen
  • Once done, return either smallest index in saved or -1 if saved is empty

Quick, elegant, concise.

Lessons learned

Getting the solution right took me longer than expected, it took me a solid morning to get this question right. This just shows how untrained and unprepared my brain is for these challenges, hopefully I can improve in the future.

Two main lessons:

  • Lesson 1. The hashmap is a super powerful generalisation. Keep your eye open for problems that you can solve using a hashmap type of solution.
  • Lesson 2. Do not forget about edge cases. Especially in the brute force one I had to hardcode many edge cases. Annoying, but a necessary part of programming.

Subscribe

Comments

You May Also Enjoy