Javascript: Use a Hash Map to solve "First Non-Repeating Character" in O(n) time

If you're struggling with LeetCode problems, algorithms and data structures, or job interview prep, hash maps are a great tool to have in your tool belt. They're fast, flexible, and easy to implement. Other languages like Ruby utilize hashes specifically, but JavaScript has Objects for a similar effect.

Today we're going to solve the "First Non-Repeating Character" problem in O(n) time and space complexity, then dig into the details of how it all works.

Let's dive right in!

First Non-Repeating Character

Problem

Write a function that takes in a string of lowercase English-alphabet characters and returns the index of the string's first non-repeating character.

The first non-repeating character is the first character in a string that occurs only once.

If the input string doesn't have any non-repeating characters, your function should return -1.

Sample Input

string = "abcdcaf"

Sample Output

1

The first non-repeating character is "b", and it is found at index 1.

Solution

We're going to want to iterate through the string and create a hashmap containing the character and its frequency.

This will look something like below, for our sample input:

{ "a": 2, "b": 1, "c": 2, "d": 1, "f": 1}

Now we have a hash containing our character:frequency pairs. If a character has a frequency greater than or equal to 2, we know that there are duplicates of that character in the string, so this entry should be deleted.

{ "b": 1, "d": 1, "f": 1 }

Now, using JavaScript's inbuilt Object methods, we should:

• find the first character of the hash

• find the index at which that character appears in the array

• return the index

In this case, that would be 1 since "b" appears as the second character in the initial array.

This problem can be solved with a time and space complexity of O(n). Code and explanations below!

Code

function firstNonRepeatingCharacter(string) {
  let obj = {}
  let split_str_arr = string.split("")

  let makeKeys = (obj, str_arr) => {
    for (let i = 0; i < str_arr.length; i++) {
      char = str_arr[i]

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

  let deleteDuplicateKeys = (obj) => {
    for (var key in obj) {
      if (obj.hasOwnProperty(key)) {
        if(obj[key] >= 2) {
          delete obj[key]
        }
      }
    }
  }

  let first;
  let answer;
  let checkAnswer = (obj, str_arr) => {
    if (Object.keys(obj).length > 0) {
      first = Object.keys(obj)[0]
      answer = str_arr.indexOf(first)
    } else {
      answer = -1
    }
  }

  makeKeys(obj, split_str_arr)
  deleteDuplicateKeys(obj)
  checkAnswer(obj, split_str_arr)
  return answer
}

Let's split this down, method-by-method.

makeKeys()

Iterate through the initial split string array and populates our obj hash with the string's character and its frequency of appearances within the string.

This will accomplish a state like:

{ "a": 2, "b": 1, "c": 2, "d": 1, "f": 1}

deleteDuplicateKeys()

Iterate through our hash map, checking first if the element exists within the hash using the hasOwnProperty method, then deleting any occurrences that have a frequency of 2 or higher.

{ "b": 1, "d": 1, "f": 1 }

checkAnswer()

Check if we have any remaining elements after deduplication, and if we have any, we use the first element in the hash map and find its original index. This gets populated into the answer variable, which will either be the index of that character's first appearance in the string, or -1.

In the case of our sample input, we know that the first character in the hash is b, so we use str_arr.indexOf("b") to find the character's index in the array and return that.

If no objects were left after the deduplication step, we'll return -1.

Final thoughts

Through this post, we've dug into the basics of implementing a Hash map in O(n) time and using it to solve a simple algorithm.

These problems can get complex and quite difficult, so always remember to take breaks and be gentle with yourself on your journey through algorithms and data structures.

Let me know if you have any other fun solutions to this problem or other fun problems to solve!