Question : Given a string, find the length of the longest substring without repeating characters.
Eg : Input = "abcabcbb" Output = 3, Since "ab...
For further actions, you may consider blocking this person and/or reporting abuse
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.