Longest substring without repeating characters, solving Google interview question.

Question : Given a string, find the length of the longest substring without repeating characters.

Eg : Input = "abcabcbb" Output = 3, Since "abc" is longest substring without repeating characters.

From the question it self, we can say that we need some sort of data structure that can keep track of unique characters.

This paves the way towards using Set

Now how to parse the string ? Notice that question asks for "substring".

If question asks for any sort of substring releated, try solving it with two pointer appraoch

Two Pointer approach

1 > This approach is simple and intuitive, for this question we will keep two pointer, left and right.
2 > We shall initialize left and right to 0.
3 > Move the right pointer by 1, and add the corresponding character to the set.
4 > If character is already present in the set then remove the character at left pointer and move the left pointer by 1.
5 > Keep on doing this till right pointer reaches the end of string.

The code is really simple and intutive :

var lengthOfLongestSubstring = function(s) {    let left = 0;    let right = 0;    let max = 0;    let set = new Set();    while(right<s.length){        if(set.has(s[right])){            set.delete(s[left]);            left++;        }else{            set.add(s[right]);            right++;            max = Math.max(max,set.size);        }    }    return max;};

That's it ! Hope you liked my explanation :)

Cracking the interviews is easy if we can see the hidden patterns :P

github : https://github.com/AKHILP96/Data-Structures-and-Algorithms/blob/master/problems/longestSubstringwithUniqueCharacters.js