Find The Length of the Longest Substring Without Repeating Characters - Javascript Solution

#javascript #algorithms #leetcode

A common interview question and although I haven't come across it in any of the interviews I have done, I have met developers who have. This is my attempt to explain the solution and how it could be solved using Javascript.

To solve the problem, we must first understand it. The question says to find the length of the longest substring without repeating characters.
So if we have "abcabcabcc", the substring that isn't repeated is "abc" because the moment we move to the next character after "c", we hit another "a" and remember, we already have hit a previous a.
So, okay, we understand now, right? Once we hit a repeated character, we should return the length of the characters before we hit the repeated one. I'm sorry to disappoint you, that's not the question. If the question asked to return the length of the first substring without repeating characters, voila, our solution above can work, but let's look at another example.
Say we have "abcabcdefghi". Now we can see that we have a different set of substrings that are not repeating. "cdefghi" are not repeating, so our answer is 7.

One way we could solve it is to have a double loop that compares the values in the substring against each other, but in almost all cases, having a loop inside a loop means bad algorithm and has a O(n^2). So how can we solve this without using a double loop?

Solution.

What are our assumptions?

We can have an empty string as input
Our input's length can be 1
How do we go from O(n^2) to O(n)?

Pseudocode

Check the length of our input, if it's empty or not a string return 0, If it's length is 1, return 1;
Have a variable that tracks the start index of the current character in our input
Have a variable that holds our length.
Create a hashTable or map that holds the current character, and it's index in the input
Loop through the input, if the current index is in the hashTable and its index is greater than or equal to the variable holding the start index, change the start index to the index after the current iteration. this will be made clear in our logic
Add the current character to the hashtable
Update the length
End the loop and return the length.

var lengthOfLongestSubstring = function(s) {

    if(!!!s.length || typeof s !== 'string' ) return 0; //if our string is empty or it's not a 
                                string, return 0
    if(s.length  == 1) return 1;//if the length is 1, return 1;

  let hashTable = {}; //our hashTable to hold our characters and index;
 let longestSubstringLength = 0; //length of longest substring
 let start = 0; //start index
 let length = s.length; //length of the array.

//convert our strings to an array;
  const strings = s.split('');


//iterate over the array
  for(let i = 0; i < length; i++) {
//if the character exist and the value of the character is greater or equal to our start index
      if(hashTable[strings[i]] !==undefined && hashTable[strings[i]] >= start) {
//change the value of start to one higher than the value of our current character 
          start = hashTable[strings[i]] + 1
      }
//add the current index and it's value to the hashTable
      hashTable[strings[i]] = i;
//find the length of the longest substring by comparing the value with the value of the current index minus the start value plus 1
      longestSubstringLength = Math.max(longestSubstringLength, (i-start + 1))
  }

/return the longestSubstringLength as our final answer
return longestSubstringLength;
}

Conclusion

With our solution above, we are ensuring we only loop once, we are also ensuring we don't have to loop if our input is not a string or if it's length is one. Is this the best solution? Certainly not, there are other ways to solve this problem. Do you have a better solution? Is there something I could improve in my logic, do you have any advice for me? Please feel free to leave a comment, I look forward to your feedback.