[Java] Longest substring without repeated characters

Given a string s, find the longest substring without repeated characters in it.

It is immediately evident that by using some O(M) extra space (M is characters in alphabet) and a sliding window approach we might be able to find our solution in O(N) time (N is length of string). We just need to determine how to correctly shrink our window when a repetition is found.

Let's look at some cases:

(1) FIRST time we encounter a repeated character (A):

i   j

A...A...

in between the As there can be any number of unique characters (even 0). The current best length is therefore j - 1, that is the whole string so far excluding ONE of the TWO repeated characters.

Since we are looking for the length, ignoring the first or second appearance of A yields the same result. As we are moving left to right, it is natural to simply ignore the first one.

(2) we have already seen this repeated character (A) AFTER our window start position (i):

 i    j

AB...AA...

now we need to ignore everything BEFORE the LAST repetition of this character since no other string between start and end of our range will be valid as all of them will contain the AA repetition, we therefore need to jump our start of range forward to exclude this situation in our future searches.

(3) we have already seen this repeated character (B) BEFORE our window start position (i):

 i     j

AB...AAB...

since the repetition for B occurred BEFORE our window start range, it is already excluded from our consideration, we therefore have nothing to do. 

 

Now we know HOW we want to shrink our window in each case, it is very important that we shrink it BEFORE updating the last known position of a repeated character, otherwise we break our logic.

You can check my implementation of findLongestSubstringWithoutRepeatingCharacters on my Gist along with some tests in LongestSubstringWithoutRepeatingCharactersJTests.