Leetcode First Unique Character in a String code optimisation

Question

I was working on First Unique Character in a String

Question

Given a string s, find the first non-repeating character in it and return its index. If it does not exist, return -1.

Example 1:

Input: s = "leetcode"
Output: 0

Example 2:

Input: s = "loveleetcode"
Output: 2

Example 3:

Input: s = "aabb"
Output: -1

My Solution

var firstUniqChar = function(s) {
    let myMap = new Map()
    for(let i = 0; i < s.length; i++){
        const val = myMap.get(s[i])
        if(!val){
            myMap.set(s[i], [i, 1])
        } else {
            myMap.set(s[i], [i, val+1])
        }
    }
    for(let entry of myMap){
        if(entry[1][1] == 1){
            return entry[1][0]
        }
    }
    return -1
};

As per my understanding the above code has time complexity O(N) and space complexity O(1). However, i get pretty bad runtimes using the above solution (tried a lot of times to check if it's issue on leetcode server end). Is there any particular part of my code that is causing this? How can i optimize this further?

Answer 1

When I execute your solution, I get a result that says that the submission is faster than ~5% of submissions and uses less memory than ~5% of submissions.

The following solution ran faster than ~94% of submissions and used less memory than ~92% of submissions.

var firstUniqChar = function(s) {
  const characterCounts = new Array(26).fill(0);
  for (let index = 0; index < s.length; index += 1) {
    characterCounts[s.charCodeAt(index) - 97] += 1;
  }

  for (let index = 0; index < s.length; index += 1) {
    if (1 === characterCounts[s.charCodeAt(index) - 97]) {
      return index;
    }
  }

  return -1;
}

I don't know the internal implementation of the Map object, so it's hard to get a sense for the instructions that are executed when a Map is created or when get or set are called on a Map, but interestingly enough, if I simply create a new Map at the beginning of my solution (see the following code block), the result is faster than ~38% of solutions. So the creation of a new Map object has a large execution cost.

var firstUniqChar = function(s) {
  new Map();
  const characterCounts = new Array(26).fill(0);
  for (let index = 0; index < s.length; index += 1) {
    characterCounts[s.charCodeAt(index) - 97] += 1;
  }

  for (let index = 0; index < s.length; index += 1) {
    if (1 === characterCounts[s.charCodeAt(index) - 97]) {
      return index;
    }
  }

  return -1;
}

If we want to avoid using a Map we could use an array to keep track of character counts. The problem states that "s consists of only lowercase English letters.". This means we only really need to keep counts for 26 different values.

To map a lowercase English letter to an array index, we can use the ASCII character code for each letter. The ASCII character code for lowercase English letters are between 97 (a) and 122 (z) inclusive. If we subtract 97 from these ASCII character codes, we have the values 0 to 25. We can use these values as the indexes of our 26 element array.

So if we iterate over each character in the input string, we can identify the ASCII character code for each character, subtract 97 to get the relevant index in our array, and increment the count at that index. This should give us the counts for all letters in the input string.

If we iterate over the characters in the input string again, we can check the array of character counts for each character. Return the index for the first character that has a count of 1.

Answer 2

Make the logic more obviously correct

This piece of code made me doubt if the logic is correct:

for(let entry of myMap){
    if(entry[1][1] == 1){
        return entry[1][0]
    }
}

My first doubt was the iteration order of Map entries. In most languages that I know, the iteration order of map data structures is undefined. I had to lookup in the docs to see that indeed Map in JavaScript remembers the original insertion order of the keys. So far so good.

My second doubt was, ok so for the program to work correctly, the entries in myMap would have to be inserted in the correct order. And they are, but I had to read and understand how myMap is populated to be convinced.

My natural approach to find the first character would be to iterate over the input string:

for (let i = 0; i < s.length; i++) {
    const [ index, count ] = myMap.get(s[i]);
    if (count === 1) {
        return index;
    }
}

Written like this, I don't have any doubts about the iteration order of maps, or how myMap was populated. It's evident that I'm iterating over letters in the correct order, so as long as myMap contains what I think it does, this code looks correct.

Written like this, I realize one more thing. I don't need the index in the map entry anymore, since I already have it, in the i variable. So I go ahead and change myMap to contain only the counts of characters. At this point, I also rename some variables to names as they feel natural:

const counts = new Map();

for (let index = 0; index < s.length; index++) {
    const letter = s[index];
    
    if (!counts.has(letter)) {
        counts.set(letter, 1);
    } else {
        counts.set(letter, counts.get(letter) + 1);
    }
}

for (let index = 0; index < s.length; index++) {
    const count = counts.get(s[index]);
    if (count === 1) {
        return index;
    }
}

This turns out to be much faster than the previous version. The significant change is that the values in the map are simple integers instead of arrays.

Checking if a map contains a key correctly

Looking at this kind of code out of context, I would suspect a possible bug. This is not the correct way to check if a map does not contain a key.

const val = myMap.get(s[i])
if(!val){

Because, if the map could contain falsy values, such as false, or 0, or '', or null, or undefined (... I hope I didn't miss anything!), then the condition would pass, and most probably that would not be intended.

The correct way:

if (!myMap.has(s[i])) {

The current code works fine because all the keys are guaranteed to be letters of the English alphabet, and none of them are falsy. As a matter of principle, it's good to build the habit of using the correct idiom when working with maps.

Answer 3

Your code is actually buggy, though correctly.

• Buggy here means the code is not what you want.
• Correctly here means it passes all testcases.

const val = myMap.get(s[i]);
if (!val) {
    myMap.set(s[i], [i, 1]);
} else {
    myMap.set(s[i], [i, val + 1]);
}

What is the value saved in the myMap? Maybe you originally meant:

The value in map is a tuple, while first value is the index of last occurrence, and the second value is the count of occurrence.

But is this true?

You may have some test by your self:

var firstUniqChar = function (s) {
    let myMap = new Map()
    for (let i = 0; i < s.length; i++){
        const val = myMap.get(s[i]);
        if (!val) {
            myMap.set(s[i], [i, 1])
        } else {
            myMap.set(s[i], [i, val + 1])
        }
    }
    return myMap;
}
console.log(firstUniqChar('aaaab').get('a'));

You will get [ 3, "2,1,0,1111" ] on the console.

Yes, your program still calculated the correct result. But maybe the string "2,1,0,1111" is not what you want anyway.

Consider a large input, you are trying to build some (maybe much larger) strings in the Map. And the JavaScript runtime have to handle these large strings (allocate memory, type convert, write memory, garbage collection...). That would cost too much times.

I haven't tested your code on LCOJ. Maybe you can fix this bug (is this a bug?) and see if it have a better performance.