First Unique Character in a String✨

Introduction

I am still on the journey of solving at least one Data Structures and Algorithm question daily on Leetcode in order to understand the concepts I am learning well and it has been very challenging and interesting since I started solving these questions.

This article will explain my solution to First Unique Character in a String on Leetcode and the logic behind my solution. Try to follow it step by step and I am sure you will understand every bit of it.

Let's dive into it 🎉

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

Step by Step Solution

Solving a Data Structures and Algorithm question requires you to think well and check your solution using different scenarios because your solution must pass all the test cases before it can be accepted.

We will solve this problem in 2 steps, which are:

• Doing Sanity Checks.
• Explaining the Logic behind our solution and writing the Code to back it up.

Sanity Checks

Before proceeding to carry out any operation we have to check the input passed to the function if it is valid.

    // Sanity Checks
    if (!s) return s;

Solution (Logic)

The Solution to this question will be in steps for easy understanding.

• Set up a hash map and store it in a variable called map.

  let map = new Map();
  

• Loop through the string and save the character in the hash map. In order to get the unique characters then we need to save it to the hash map differently. If a character in the string is unique we will save it by index but if it is repeated we will save it by -1.

      for(let i = 0; i < s.length; i++) {
        if(map.has(s[i])) {
          map.set(s[i], -1);
        } else {
          map.set(s[i], i);
        }
      }

• The next step is to iterate through the map using for of in JavaScript but to iterate through a map and get the value you will need to use the syntax below.

const iterable = new Map([['a', 1], ['b', 2], ['c', 3]]);

for (const [key, value] of iterable) {
  console.log(value);
}
// Output
// 1
// 2
// 3

• Since we know how to iterate through a map, we will iterate through the map and get the value that is -1, the next thing is to return the value we got and since the value was stored as the index then we have gotten our solution.

    for(let [key, value] of map) {
        if(value !== -1) {
          return value;
        }
      }

• The Final Step is to return -1 if none of the condition above is met and this is as instructed by the question.

You can check through compilation of the code below

 // Sanity Checks
    if (!s) return s;

     let map = new Map();

      for(let i = 0; i < s.length; i++) {
        if(map.has(s[i])) {
          map.set(s[i], -1);
        } else {
          map.set(s[i], i);
        }
      }

      for(let [key, value] of map) {
        if(value !== -1) {
          return value;
        }
      }

     return -1;

The Time and Space Complexity

Time Complexity

This Solution has a Time complexity of O(n) which is a Linear time since we go through the string of length N two times.

Space complexity

The Space Complexity is O(1) which is constant time because English alphabet contains 26 letters.

The Runtime is 144ms, faster than 34.50% of JavaScript online submissions for First Unique Character in a String and Memory Usage: 41.4 MB, less than 97.36% of JavaScript online submissions for First Unique Character in a String.

Conclusion

I hope you have learnt a lot from this article and your contribution is also highly welcomed because we get better by learning from others, you can reach out to me on Twitter here . Watch out for more helpful contents on Data Structures and Algorithm from me.

Don't forget to Like, share and subscribe for more articles in this series called Solutions to Data Structures and Algorithm Questions on Leetcode.

Enjoy 🎉