Examples / Sliding window▶Run in PyTrace
Sliding Window Visualization in Python
A sliding window is a range [left, right] over an array or string that you extend on one side and shrink on the other, so that each element enters and leaves the window at most once.
Here the window must never contain a repeated character. right moves forward on every iteration; whenever the new character is already in the window, left advances and removes characters from the seen set until the duplicate is gone.
ComplexityO(n) time: each character is added and removed at most once.
class Solution:
def lengthOfLongestSubstring(self, s: str) -> int:
seen = set()
left = best = 0
for right in range(len(s)):
while s[right] in seen:
seen.remove(s[left])
left += 1
seen.add(s[right])
best = max(best, right - left + 1)
return bestInputs
s"abcabcbb"
expected3
What to watch
leftandrightas pointers over the string, marking the current window- The
seenset gaining and losing characters as the window moves bestupdating only when the window reaches a new maximum length