Teaching to learn: First Unique Character in a String

Leetcode: First Unique Character in a String

This post is part of series where I will be breaking down coding problems that I have solved and sharing the lessons I learned while finding an answer. The coding language will be in JavaScript.

Ahh strings. I used to hate working with them but I have grown to cherish their quirks in JavaScript. This challenge’s title screams at you: YOU WILL BE LOOPING OVER THE ENTIRE GIVEN STRING. Immediately that tells me our time complexity will probably be O(n). In this article, I will detail two solutions. My first-thing-to-pop-in-my-head solution and a slightly different approach. Here we go!

This challenge can be found here.

Understanding the problem

We are provided a very blunt description of what is expected from us, so I will quote verbatim:

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

“Note: You may assume the string contain only lowercase letters.”

Alright simple enough. We are looking for the FIRST non-repeating character in the string. For example, if the string input is “leet” then the FIRST non-repeating character would be….. the “l”! Ding ding ding.

But what if that example was spelled with two l’s? Another example: “leelt”. (I know that is not a real word and this is very contrived but so are most of these challenges so hang in there)

Since there are two l’s in “leelt”, the first non-repeating character is now… “t”! Yea! We are on a roll.

We have our premise and examples… but how would the function know if a character is the first non-repeating character right off the bat? Well, the function wouldn’t. The function is going to have check every character in the string. Computers cannot predict the future. They have to “see” what we are looking at in order to give accurate results.

My mind wanders to a hash map. Yes, the space-consuming structure that is usually the saver of time complexity. We have the extra space to spare here so let us utilize it!

We have our understanding, let’s get to the planning.

Pseudo-code:

I will now make a short list of steps needed to implement our code:

1. Initialize the hash map: let uni = new Map();
2. Loop over the length of the input string s: If uni has the current index of s, update it’s value to be -1. Otherwise, set the current index of s with a value of 1.
3. Get the iterator object of uni and use a while loop to move through the iterator object until a value that is NOT -1 is found. (There are multiple ways to do this, my implementation can be seen in the actual code later on)
4. Return the current value from the iterator object IF it is NOT undefined. If it is undefined, return -1.

Now let’s see the hard proof.

The code:

O(n) time / O(1) space, since there is a max of 26 letters in the English Alphabet

To move through the iterator object, I used two variables vals and current. The first variable vals is the actual iterator object (it contains all the values of every key in the hash map: in insertion order *this is important*). The second variable current is the first value of the first key in the hash map.

Since Maps maintain insertion order in JavaScript, we can use this method to get the first non-repeating character in the Map by looping through it with a while loop. Since we chose to use -1 as an indicator that the character is NOT unique in the given string, every time we see a -1 we continue to move to the next value in the iterator object.

If we ever find a value that is not -1, the while loop breaks and we return the current variable. If we loop all the way through every value in the iterator object, eventually current will be set to undefined and our loop will break. The ternary operator in our return statement will see that current is undefined, and return -1 since no unique character was ever found in the given string.

Time complexity would be O(n) since we are touching every character in the given string “s”. Space complexity would be O(1) since we are only ever going to have a maximum of 26 letters stored in our Map (assuming we are working with lowercase English Alphabet only, in this case we are).

Another solution:

We can approach this problem with an assumption: that we are only dealing with the English alphabet.

Since we know that there are 26 distinguished letters in the English Alphabet, we can use that hard number to create a Map of every letter in the Alphabet, and assign values to each number as we encounter them.

That is pretty much all there is to it, let’s look at the steps in pseudo code!

1. Initialize an array with 26 indices (for each letter of the alphabet)
2. Fill each index with 0
3. Loop over length of input s and add 1 to the value of the index for that given character (a = index 0, b = index 1, c = index 2, d = index 3, e = index 4)
4. Loop over the length of input s again and search for the index that has a value of 1, return that index if 1 is found
5. Return -1 if nothing was found

O(n) time / O(1) space since we have a max of 26 indices

Now you will notice that I did not mention how we would get the index for each letter in the pseudo-code steps. If you look at the code above, you will see that in each for loop I have a variable index which is defined by the difference of character codes at the current i and ‘a’.

The character code of lowercase ‘a’ in JavaScript is 97. You can view a chart of JavaScript character codes here. Every letter after ‘a’ in the alphabet is +1 from it’s previous letter.

For example, ‘b’ is 98. 98–97 = 1. So ‘b’ is index 1 in our letters Array.

‘a’ is 97, so 97–97 = 0. ‘a’ is index 0 in our letters Array.

‘z’ is 122 so 122–97 = 25. ‘z’ is 25 in our letters Array. (This makes sense because if ‘a’ is index 0, then ‘z’ being the last letter would be index 25).

This is a fun mathematical-ish way of getting a solution. Whenever I submitted this second solution, it appeared to be a bit faster than my original solution which uses a Map. I assume that is so because Array’s are stored sequentially in memory whereas Hash Maps are not.

My original solution actually uses less space, since it only stores the letters that are actually in the given string. This alternate solution stores all 26 ‘letters’ every time it is called.

So there you have it! Pros and cons. Choose the solution that works best for your given situation. Always look at more than one solution where possible! It helps you to learn, keeps you on your toes, and offers options. I like options. Do you?

If you have another way of solving this challenge, let me know. Any advice is also appreciated. Take care!