DEV Community

Longest substring without repeating characters, solving Google interview question.

Akhil on June 21, 2020

Question : Given a string, find the length of the longest substring without repeating characters. Eg : Input = "abcabcbb" Output = 3, Since "ab...
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.