# Leetcode problem 378 First unique character in a string

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.

Tags:

Categories:

Updated: