The sliding window technique maintains a contiguous range [left, right] over a sequence, expanding and contracting to find an optimal subrange. A variable-size window adjusts its size dynamically based on a constraint.
Use when: you need to find the longest or shortest contiguous subarray/substring satisfying some condition.
Find the longest substring where all characters are
unique. We expand the window by moving right, and
contract by moving left when we see a duplicate.
Map from character to its most recent index.
This lets us jump left directly past the
duplicate instead of sliding one step at a time.
If this character was seen at or after left,
it’s a duplicate within our window. Shrink the
window by moving left past the duplicate.
Check if this is the longest valid window so far.
Trace: s = “abcabcbb”
right=0: ‘a’, window=“a”, best=1 right=1: ‘b’, window=“ab”, best=2 right=2: ‘c’, window=“abc”, best=3 right=3: ‘a’, seen at 0, left=1, window=“bca”, best=3 right=4: ‘b’, seen at 1, left=2, window=“cab”, best=3 …
func longestUniqueSubstring(s string) int {
lastSeen := make(map[byte]int)
best := 0
left := 0
for right := 0; right < len(s); right++ {
ch := s[right]
if idx, ok := lastSeen[ch]; ok && idx >= left {
left = idx + 1
}
lastSeen[ch] = right
if windowLen := right - left + 1; windowLen > best {
best = windowLen
}
}
return best
}
func main() {
fmt.Println(longestUniqueSubstring("abcabcbb"))
fmt.Println(longestUniqueSubstring("bbbbb"))
fmt.Println(longestUniqueSubstring("pwwkew"))
}