Akhil

Posted on

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{
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

Muhimen

O(n) solution. I don't know any better solution. Good enough for length 10^6 nightmare if the length exceeds 10^9.
sorry for comparing too large test cases. Doing CP all the time makes me think how can I avoid TLE ðŸ˜…

Akhil

For the length > 10^9 maybe using something like HashSet or hashmap will be much better. Do you know any other better method?

Muhimen

This problem can be compared with the "Maximum increasing subarray" where you need to check all the elements. So, probably, there isn't a better solution than O(n)(or I don't know if exists).
One thing I can confirm, the length of the maximum subarray for this problem will not exceed 26 ðŸ˜‹

Akhil

hmm, then making a boolean array of length 26 makes more sense compared to adding and deleting characters from set. I don't think there's a better solution than O(n) so optimizing storage might be the only way.

Muhimen

Yes indeed. We can make an array of length 26 all of them will be false.
Once we see a character, we make the respective index true. And continue. If an element is already true, reset the array to false.

I think the storage, in this case, will be O(1) as we are working with the same array all the time.

Daniel Worsnup

Great write-up, thanks so much for sharing! It could be worth mentioning that the general approach used here is called a "sliding window" and is very common among solutions to competitive programming problems.

Theofanis Despoudis

Epic!

Akhil

Thanks !

Shyam Salil

Is this for the longest continuous substring?

Nam Hoang Le

Yes it is

Shyam Salil

Really cool one :) Love your solution! I always preferred a hash-map solution, but seeing a different one definitely sparked one in me! Cheers :)

Akhil

Saurabh Sharma

Why dont they just ask people to write code (of their domain) and check on based on code of domain rather than some abstract problem.

Akhil

This question was asked for a generalist SWE interviews. If a person applies for a Frontend developer / a Backend developer / NoSQL developer, then questions related to those fields are asked.

Generally, people go with Generalist interview because :
1 > domain related questions go in-depth.
2 > to ask such a question you need a person who knows ins and outs of the domain so someone senior level.
3 > if a domain expert is interviewing you, that means he has taken time out of his daily project goals to interview you, which means a delay in reaching goals and a break of flow.
4 > They want someone who could think about solving the problem irrespective of domain and many real-world applications use algorithms and data structures.

Saurabh Sharma

Makes sense

jrogers8835 • Edited

Fair question, I don't work for google but I've done tons of coding interviews for the company I work for and here are a few issues I ran in to when I tried domain coding problems:
1) if they provide the company value, then they're supposed to be paid