DEV Community

Akhil
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{
            set.add(s[right]);
            right++;
            max = Math.max(max,set.size);
        }
    }
    return max;
};
Enter fullscreen mode Exit fullscreen mode

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

Top comments (16)

Collapse
 
muhimen123 profile image
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 😅

Collapse
 
akhilpokle profile image
Akhil

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

Collapse
 
muhimen123 profile image
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 😋

Thread Thread
 
akhilpokle profile image
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.

Thread Thread
 
muhimen123 profile image
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.

Collapse
 
worsnupd profile image
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.

Collapse
 
theodesp profile image
Theofanis Despoudis

Epic!

Collapse
 
akhilpokle profile image
Akhil

Thanks !

Collapse
 
shyams1993 profile image
Shyam Salil

Is this for the longest continuous substring?

Collapse
 
namhle profile image
Nam Hoang Le

Yes it is

Collapse
 
shyams1993 profile image
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 :)

Thread Thread
 
akhilpokle profile image
Akhil

Thanks for reading! :)

Collapse
 
itsjzt profile image
Saurabh Sharma

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.

Collapse
 
akhilpokle profile image
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.

Collapse
 
itsjzt profile image
Saurabh Sharma

Makes sense

Collapse
 
jrogers8835 profile image
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
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.