How do you find the longest substring without repeating characters using a sliding window?
You keep a window of characters that has no repeats, and you move the window along one character at a time.
def longest_unique(text):
last_seen = {}
best = 0
start = 0
for index, letter in enumerate(text):
if letter in last_seen and last_seen[letter] >= start:
# This letter repeats inside the window, so move the start
# past the place where it was last seen.
start = last_seen[letter] + 1
last_seen[letter] = index
length = index - start + 1
if length > best:
best = length
return best
So how does it work? The window runs from start to the character you are looking at, and it never has a repeat in it. When you meet a letter that you have already seen inside the window, you have to move the start past that earlier copy. The dictionary tells you where the earlier copy was, so you do not have to search for it.
And the complexity is O of n for the time, because you go through the text once and every step is a constant amount of work, and O of k for the space, where k is the number of different letters in the text.
The next two questions in this topic show a shorter version and a close relative of the problem.