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

First Unique Character in a String (TypeScript)


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:

function firstUniqChar(s: string): number  {


};

Solution 1

At first, let's solve this by using a hash table aka object in JavaScript.

The idea is to go thru the string and store how many times a letter appears in the string.

const hashTable = {}

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

    if (hashTable[char]) {
        hashTable[char]++
    } else {
        hashTable[char] = 1
    }
}

At first, it might look alright but there is a problem with the code above.

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++) {
    if (hashTable[s[i]] === 1) {
        return i
    }
}

return -1

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

function firstUniqChar(s: string): number {
    const hashTable = {}

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

       if (hashTable[char]) {
           hashTable[char]++
       } else {
           hashTable[char] = 1
       }
   }

    for (let i = 0; i < s.length; i++) {
        if (hashTable[s[i]] === 1) {
            return i
        }
    }

    return -1
};

Let's submit it and see the result.

Line 7: Char 12: error TS7053: Element implicitly has an 'any' type because expression of type 'any' can't be used to index type '{}'.
Line 8: Char 12: error TS7053: Element implicitly has an 'any' type because expression of type 'any' can't be used to index type '{}'.
Line 10: Char 12: error TS7053: Element implicitly has an 'any' type because expression of type 'any' can't be used to index type '{}'.
Line 15: Char 13: error TS7053: Element implicitly has an 'any' type because expression of type 'string' can't be used to index type '{}'.

Oh shoot, we got an error 🥵.

If we look at the error message we would see that the problem is with types.

We didn't provide our hash table with type.

const hashTable = {}

We could solve it just by adding any to hashTable

const hashTable: any = {}

But in this case, it's a bad practice to use any type. According to the docs we may use any type if we need to describe the type of variables that we do not know when we are writing an application.

So, let's fix it by adding the right type. We know that hash table is an object and its key is a string and its value is a number. Let's add an interface to our solution.

interface HashTableInterace {
    [key: string]: number;
}

const hashTable: HashTableInterace = {}

Let's submit it and see the result.

Runtime: 112 ms, faster than 86.84% of TypeScript online submissions for First Unique Character in a String.
Memory Usage: 41 MB, less than 100.00% of TypeScript 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.

function firstUniqChar(s: string): number {

    for(let i = 0; i < s.length; i++) {
        if(s.indexOf(s[i]) === s.lastIndexOf(s[i])) {
            return i
        }
    }

    return -1
}

Let's submit it and see the result.

Runtime: 92 ms, faster than 100.00% of TypeScript online submissions for First Unique Character in a String.
Memory Usage: 40.8 MB, less than 100.00% of TypeScript online submissions for First Unique Character in a String.
© 2021, Andrew Losseff