Home > leetcode > First Unique Character in a String (JavaScript)

First Unique Character in a String (JavaScript)


Today we solve a very popular 'kata' on Leetcode #387 First Unique Character in a String

Difficulty level: Easy

Related Topics: Hash Table, String

Disclaimer: You might have different results in Runtime and Memory Usage, it's okay 🤣 it how it works.


Description:

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

Examples:

s = "leetcode"
return 0.

s = "loveleetcode"
return 2.

Note:

 You may assume the string contains only lowercase English letters.

And your playground looks like this:

var firstUniqChar = function(s) {


};

Solution 1

I'll walk you thru the process of how I solved it.

At first, we'll count how many times a letter appears in the string. And we store results into an object.

const letterCounter = {}

Now use a loop and store result in letterCounter

  for(const letter of s) {
    if(letterCounter[letter]) letterCounter[letter]++
    else letterCounter[letter] = 1
  }

And our object looks like this:

  c: 1,
  d: 1,
  e: 3,
  l: 1,
  o: 1,
  t: 1

Now we have to return the first unique character, but as you can see object doesn't guarantee order. That's why we have to loop over the string and find the first letter with value 1. Or return -1 if there is no unique character.

  for( let i = 0; i < s.length; i++) {
    const stringLetter = s[i]

    if (letterCounter[stringLetter] === 1) {
        return i
    }
  }

We go thru string letter by letter and check where this letter has value 1 in letterCounter if so, we return its number.

Full solution

var firstUniqChar = function(s) {

    const letterCounter = {}

  for(const letter of s) {
    if(letterCounter[letter]) letterCounter[letter]++
    else letterCounter[letter] = 1
  }

  for( let i = 0; i < s.length; i++) {
    const stringLetter = s[i]

    if (letterCounter[stringLetter] === 1) {
        return i
    }
  }

  return -1

};

Let's submit it and see the result.

Runtime: 108 ms, faster than 72.55% of JavaScript online submissions for First Unique Character in a String.
Memory Usage: 40.6 MB, less than 36.36% of JavaScript online submissions for First Unique Character in a String.

Solution 2

Let's try a different approach.

In JavaScript we have String.prototype.indexOf() and String.prototype.lastIndexOf().

If indexOf() equal lastIndexOf() this is a unique character. So we have to loop over the string and return first unique character.

var firstUniqChar = function(s) {

   for( let i = 0; i < s.length; i++) {
       const letter = s[i]

       if(s.indexOf(letter) === s.lastIndexOf(letter)) {
           return i
       }
   }

    return -1

};

Let's submit it and see the result.

Runtime: 172 ms, faster than 17.54% of JavaScript online submissions for First Unique Character in a String.
Memory Usage: 38.4 MB, less than 90.91% of JavaScript online submissions for First Unique Character in a String.

Solution 2 with String.prototype.substring()

var firstUniqChar = function(s) {

    for(let i = 0; i < s.length; i++) {
       if( s.indexOf( s.substring(i, i + 1) ) === s.lastIndexOf( s.substring(i, i + 1) ) ) {
           return i
       }
   }

   return -1

};

Let's submit it and see the result.

Runtime: 128 ms, faster than 41.86% of JavaScript online submissions for First Unique Character in a String.
Memory Usage: 39.7 MB, less than 56.68% of JavaScript online submissions for First Unique Character in a String.

An idea to improve our solution

We know that we can get an empty string. Let's first check it, then start to search for unique characters.

We can add this line of code if (s.length === 0) return -1; to the code.

var firstUniqChar = function(s) {
    if (s.length === 0) return -1;

    for( let i = 0; i < s.length; i++) {
       const letter = s[i]

       if(s.indexOf(letter) === s.lastIndexOf(letter)) return i
   }

   return -1

};

Best result!

Runtime: 92 ms, faster than 94.86% of JavaScript online submissions for First Unique Character in a String.
Memory Usage: 39.2 MB, less than 73.26% of JavaScript online submissions for First Unique Character in a String.
© 2021, Andrew Losseff