Longest Substring Without Repeating Characters

I have recently started attempting one LeetCode LeetCode problem everyday, to keep me "in shape".

Today's task? To find the length of the longest substring without any duplicate characters.

Here's my solution process:

• Loop through giving string (s) while counting characters, and break if a duplicate is found
• Use a hash-map (in this case, a javascript object) to store the unique characters

let uniqueChars = {}
let length = 0;
for(let i=0; i<s.length; i++){
  let char = s.charAt(i)
  if(uniqueChars[char]) {break;}
  else {
     uniqueChars[char] = true
     length ++
  }
}
return length;

Now, we're not done, because we are assuming that the longest substring starts from the first index (!).
So, to account for that, we'll need to make it into a recursive function where we keep slicing the string till the end, and compare the lengths.

Looks like this:

var lengthOfLongestSubstring = function(s) {
    if(s.length <= 1) return s.length  //for 1-letter or empty strings
    let uniqueChars = {}
    let length = 0;
    let counter = 0
    for(let i=0; i<s.length; i++){
        let char = s.charAt(i)
        if(uniqueChars[char]) {break;}
        else {
            uniqueChars[char] = true
            length ++}
    }
    if (length >= s.length -1) return length
    return Math.max(length, 
         lengthOfLongestSubstring(s.slice(++counter)))
};

Let's break this down:

• From index, counter, we loop through string UNTIL there's a duplicate or we reach the end.
• After the loop, we check if the length of our substring is at least 1 less than the string length. If true, we can stop searching, because this is our max length.
• Otherwise, we call the function again, moving the counter a step forward, and return the maximum of both lengths. This happens until the counter is at the last letter.

As you can probably tell, this method has a time-complexity of O(n^2), as we have to loop through the rest of the string at every index. 👎

I will be updating this with a faster algorithm, but please feel free to let me know your suggestions!