DEV Community

Discussion on: Longest substring without repeating characters, solving Google interview question.

Collapse
akhilpokle profile image
Akhil Author

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 Author

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.