Top Interview Question: Finding the First Unique Character in a String using Linear Time

Today's algorithm is the First Unique Character in a String problem:

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

For example, if you were given the string "APPLESAUCE", the first unique character is "L" at index 3, since "L" is only found once in the string, and it comes before any other unique characters.

This problem is listed on Leetcode's Top Classic Interview Questions list. Like most questions that are frequently found in technical interviews, this one can be solved in a number of different ways. Today, I'll solve it in JavaScript using a hash. Hashes are very useful data structures when solving algorithms because looking up and storing variables in a hash takes up little space (O(n)), and is done in a short amount of time (O(1) on average). (If you're interested in Big O complexity, you should check out this cheat sheet.)

In this post, I'll discuss my approach to this problem, and then will code the solution. This approach will end up taking linear time (O(n)).

Approaching the Problem

A hash is useful for problems that ask you to find unique values because you can quickly store elements and their frequency. In this algorithm, we want to take a string, and count how many times each character in the string appears. We can do this by creating an empty hash and then iterating through the string, checking if each letter is already a key in the hash. If the letter is already in the hash, we'll increment its value, since we found the same letter another time. If the letter is not already a key in the hash, that means we haven't yet seen it in the string, so we'll set its value in the hash equal to 1.

To see this method on a smaller scale, let's say you're given that string = ABA, and you want to create a hash that stores how many times each letter is found in the string. We'd start by creating an empty hash, called letterHash. We'd then want to use a for loop to go through each element in the string, and check to see if it's already in the hash. If it is in the hash, we can increment its value. If it's not in the hash, we'll initialize the letter as a key in the hash, and set its value equal to 1.

// initialize an empty hash
let letterHash = {};
// use a for loop to check each letter in the string
for (let i = 0; i < string.length; i++) {
  // if that letter is already found in the hash...
  if (string[i] in letterHash) {
    // ...then increment its value by 1
    letterHash[string[i]]++;
  } else {
    // otherwise, initialize it in the hash, setting its value equal to 1
    letterHash[string[i]] = 1;
  }
}

This would give us the result of letterHash = {"A": 2, "B": 1}.

Now, we want to check which is the first unique element in the string. There's a few ways to go about this, but one would be to go through the hash a second time. At each letter, check the hash to see what the value for that letter is. The value indicates how many times that letter has been seen in the string. If the value is 1, then we know it's unique, so we can return that index. We know that we're returning the first unique index because we're using a for loop, going from the start to the end of the string, which means we'll find the first unique character first.

Coding the Solution

We'll start by initializing an empty hash, and setting up the first for loop.

function firstUniqChar(s) {
    let hash = {};
    for (let i = 0; i < s.length; i++) {
        //...
    }
    //...
}

In the for loop, we'll check each letter of s to see if it's in hash. We can access each letter with s[i], since i is the index. If the letter is in hash, we'll want to increment its value, since we found a letter multiple times. If it's not in hash, we'll initialize the value, setting it equal to 1.

function firstUniqChar(s) {
    let hash = {};
    for (let i = 0; i < s.length; i++) {
        if (s[i] in hash) {
            hash[s[i]]++;
        } else {
            hash[s[i]] = 1;
        }
    }
    //...
}

We now have a hash whose keys are each letter in the string, and values are the number of times those letters are found in the string. Next, we'll want to set up a second for loop, going through the string again. In this for loop, we'll want to see what the value is for that letter in hash. If the value of that letter is 1, then we know it was only found once in the string, so we can return its index, i.

function firstUniqChar(s) {
    let hash = {};
    for (let i = 0; i < s.length; i++) {
        if (s[i] in hash) {
            hash[s[i]]++;
        } else {
            hash[s[i]] = 1;
        }
    }
    for (let i = 0; i < s.length; i++) {
        if (hash[s[i]] === 1) {
            return i;
        }
    }
    //...
}

If there were no instances of a letter having a value of 1 in the hash, that means there are no unique characters in the string. As per the instructions, if that's the case, then we should return -1.

function firstUniqChar(s) {
    let hash = {};
    for (let i = 0; i < s.length; i++) {
        if (s[i] in hash) {
            hash[s[i]]++;
        } else {
            hash[s[i]] = 1;
        }
    }
    for (let i = 0; i < s.length; i++) {
        if (hash[s[i]] === 1) {
            return i;
        }
    }
    return -1;
}

Even though we went through the string two times, the time complexity is still O(n) (rather than O(2n) or O(n²)). It's not O(2n) because coefficients (in this case, the 2) are removed in Big O notation for simplicity. It's not O(n²) because the for loops are not nested--we go through the string two separate times, not at the same time.

Let me know in the comments if you have questions or alternate solutions to this problem!

Comments

[Saloni Yadav]

leetcode.com/problems/elimination-...

Hi Alisa,
Can you please explain the above problem and its solution in one of your posts soon?
Thank you :)

[Muhammed Maher]

I personally faced this problem in my last job's code interview, I half solved it as I was very nervous, but I got the job nonetheless, now It all makes sense to me, thanks for sharing :)