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
Top comments (16)
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 😅
For the length > 10^9 maybe using something like HashSet or hashmap will be much better. Do you know any other better method?
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 😋
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.
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.
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.
Epic!
Thanks !
Is this for the longest continuous substring?
Yes it is
Really cool one :) Love your solution! I always preferred a hash-map solution, but seeing a different one definitely sparked one in me! Cheers :)
Thanks for reading! :)
I never understand why google asks this kind of question?
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.
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.
Makes sense
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
2) often time domain related problems require too much background... you spend half the interview answering questions about domain concepts instead of seeing them perform
3) the domain itself could be proprietary or the related code.
Generally speaking domain is easy enough to teach in my experience. When I'm interviewing I want to strip away they business stuff and see if you can convert a problem to working code. How efficiently you do that (and communicate what you do) speaks volumes.