How to find the first unique character in a string

Introduction

This is a basic string related interview question that can be asked.

You will be given a string and you have to find the first unique character going left to right.

Step 1: Let’s take a look at the leetcode problem statement

Step 2: The first approach is to make a custom object to store different characters, the number of their occurrences and their last index

Step 3: So in the code below, we will iterate over the string and keep store custom objects in a LinkedHashMap.

The good thing about LinkedHashMap is that it maintains order of insertion. So in the end, when all characters are put in the map, we will start iterating over keys in LinkedHashMap and the first character with numOccurence == 1 will be our answer.

Step 4: Performance analysis of custom object solution on leetcode, 6.94% which is really bad! Let’s try something else.

Step 5: My second approach is to check for first and last index of a character. When both indexes are the same, we have found our answer. Easy right? Sometimes we complicate things while the answer is really simple.

Step 6: Let’s analyze the new solution on leetcode. In my attempt, it gave me 6.72%, which is even worse. That’s doesn’t seem to be right, something is off!

Step 7: I didn’t know what to do with this so I checked leetcode’s official solution. They are basically counting occurrences of each character and storing in a map and then iterating string again to lookup count, if count == 1, answer found!

Step 8: Now, I was expecting this solution to perform better in leetcode’s analyzer, but… see the results for yourself.

Faster than 5.06% of all java submissions!

There’s something wrong with the analyzer, I believe.

Final words

If you like this post, follow me on instagram: https://www.instagram.com/global.software.developers/?hl=en