Sliding Window

One-liner: keep a moving range of the input valid, and update it incrementally instead of recomputing it from scratch.

The analogy

Imagine looking at a long train through a rectangular window on a platform. You never re-count every carriage when the train moves — you only notice one carriage entering on the right and one leaving on the left. A sliding window does exactly that with a subarray or substring: each element enters once and leaves once, so the whole scan is O(n) instead of O(n²).

Recognition signals

Reach for a sliding window when you see all of these:

1. The answer is about a contiguous range — a subarray or substring (not a subsequence).
2. You are asked for the longest, shortest, maximum, minimum or count of such ranges.
3. Whether a range is "valid" can be maintained incrementally — adding an element or removing one updates a small piece of state (a count, a sum, a set of seen characters).

Step-by-step walkthrough

Take Longest Substring Without Repeating Characters on "abcabcbb":

1. Start with an empty window (left = 0).
2. Move right one step at a time. The new character enters the window.
3. If it duplicates something already inside the window, the window is invalid — move left forward until it is valid again.
4. After the window is valid, record its length.
5. Repeat until right reaches the end.

The two edges only ever move forward. That is the whole reason it is linear.

Code template

The shape is always the same — only the three marked spots change per problem.

// Template for a variable-size window. Fill in the three marked spots.
func slideTemplate(items []int) int {
	best, left := 0, 0
	for right := 0; right < len(items); right++ {
		// 1. ADD items[right] to the window state
		for false /* 2. window is INVALID (or, for "shortest": GOOD) */ {
			// 3. REMOVE items[left] from the window state
			left++
		}
		best = max(best, right-left+1) // 4. record the answer
	}
	return best
}

Why each part exists:

See it run

Watch the template solve a real problem. Try the presets — "abba" is the classic trap, where left must never move backwards.

// LengthOfLongestSubstring: longest substring without repeating characters.
// Variable window: grow right every step, shrink left while the window is invalid.
func LengthOfLongestSubstring(s string) int {
	last := map[byte]int{} // char -> index where it was last seen
	best, left := 0, 0
	for right := 0; right < len(s); right++ {
		if i, seen := last[s[right]]; seen && i >= left {
			left = i + 1 // jump past the previous copy: window is valid again
		}
		last[s[right]] = right
		best = max(best, right-left+1)
	}
	return best
}

The real solution

// LengthOfLongestSubstring: longest substring without repeating characters.
// Variable window: grow right every step, shrink left while the window is invalid.
func LengthOfLongestSubstring(s string) int {
	last := map[byte]int{} // char -> index where it was last seen
	best, left := 0, 0
	for right := 0; right < len(s); right++ {
		if i, seen := last[s[right]]; seen && i >= left {
			left = i + 1 // jump past the previous copy: window is valid again
		}
		last[s[right]] = right
		best = max(best, right-left+1)
	}
	return best
}

Instead of a for loop that shrinks one step at a time, we remember where each character was last seen and jump left past it. The i >= left check is the subtle part: a character seen before the window started is not a conflict.

Variations

Fixed-size window — the size is given (k), so remove one element every time you add one:

// MaxSumSubarray: largest sum of any k consecutive numbers.
// Fixed window: add the entering element, subtract the leaving one.
func MaxSumSubarray(nums []int, k int) int {
	if k <= 0 || k > len(nums) {
		return 0
	}
	sum := 0
	for i := 0; i < k; i++ {
		sum += nums[i]
	}
	best := sum
	for right := k; right < len(nums); right++ {
		sum += nums[right] - nums[right-k]
		best = max(best, sum)
	}
	return best
}

Shortest valid window — shrink while the window is good, recording the answer each time:

// MinSubArrayLen: shortest subarray with sum >= target (all nums positive).
// Shrink while the window is *good*, recording the answer each time.
func MinSubArrayLen(target int, nums []int) int {
	best, sum, left := len(nums)+1, 0, 0
	for right, v := range nums {
		sum += v
		for sum >= target {
			best = min(best, right-left+1)
			sum -= nums[left]
			left++
		}
	}
	if best == len(nums)+1 {
		return 0
	}
	return best
}

Coverage window — "contains everything in t". Track how many required characters are still missing; the window is valid when that hits zero:

// MinWindow: smallest substring of s containing every char of t (with multiplicity).
func MinWindow(s, t string) string {
	if len(t) == 0 || len(t) > len(s) {
		return ""
	}
	need := [128]int{}
	for i := 0; i < len(t); i++ {
		need[t[i]]++
	}
	missing := len(t) // how many required chars the window still lacks
	bestStart, bestLen, left := 0, len(s)+1, 0
	for right := 0; right < len(s); right++ {
		if need[s[right]] > 0 {
			missing--
		}
		need[s[right]]--
		for missing == 0 { // window is valid: try to shrink it
			if right-left+1 < bestLen {
				bestStart, bestLen = left, right-left+1
			}
			need[s[left]]++
			if need[s[left]] > 0 {
				missing++
			}
			left++
		}
	}
	if bestLen > len(s) {
		return ""
	}
	return s[bestStart : bestStart+bestLen]
}

Complexity

right moves n times and left moves at most n times in total, even though left sits inside a loop — that is amortized O(n), not O(n²).

Common mistakes

Practice ladder

Notice: these are ordered Easy → Hard, and none of the titles say "window". Decide why each one qualifies before you code it.

1. 1.
   Maximum Average Subarray I

   Fixed size — what enters, what leaves?
   Easy
2. 2.
   Longest Substring Without Repeating Characters
   Medium
3. 3.
   Minimum Size Subarray Sum

   Shortest → record while shrinking.
   Medium
4. 4.
   Longest Repeating Character Replacement

   The invalid condition involves a budget of k.
   Medium
5. 5.
   Permutation in String
   Medium
6. 6.
   Minimum Window Substring
   Hard
7. 7.
   Sliding Window Maximum

   The window state needs more than a count — what structure gives you the max cheaply?
   Hard

Which pattern? Drills

Unlabeled problems — pick the pattern, then read why.