Sliding Window
Look at a long train through a window: when it moves one carriage enters and one leaves, and you never recount the whole train. For problems about a contiguous subarray or substring, you grow the window on the right and shrink it on the left while keeping a small running summary.
After this topic: You can maintain a valid window with a counter, set or map and decide when to record the best answer.
Do these first: Two Pointers
Step 1 · Read the lesson
Keep a moving range valid and update it incrementally instead of recomputing.
Step 2 · Solve the problems in order
Try each one for about 20 minutes first. Problems with a Run code tab are checked right here. If you are stuck, open Nudge, think again, then Idea. Go skeleton only gives the function shape, and Reference solution is for comparing after you have tried. Tick the box when you could solve it again without help.
- 1.Best Time to Buy and Sell StockEasy
You must buy before you sell. As you walk the days, what single number must you remember?
Track the lowest price so far; at each day the best profit is price − lowest; keep the maximum.
Target: O(n) time, O(1) space
Types such as ListNode, TreeNode and Node are the standard ones for these problems. Define them yourself if you run the code locally.
func maxProfit(prices []int) intTested with go test. Try it yourself first, then compare.
// MaxProfit: the best sale on day i uses the cheapest price BEFORE day i, so remember the minimum so far. func MaxProfit(prices []int) int { best, lowest := 0, 1<<60 for _, p := range prices { lowest = min(lowest, p) best = max(best, p-lowest) } return best } - 2.Longest Substring Without Repeating CharactersMedium
When a character repeats inside your window, where must the left edge move to?
Map char→last index. When the new char was last seen inside the window, jump left to last+1. Record right−left+1.
Target: O(n) time, O(k) space
Types such as ListNode, TreeNode and Node are the standard ones for these problems. Define them yourself if you run the code locally.
func lengthOfLongestSubstring(s string) intTested with go test. Try it yourself first, then compare. It is explained step by step on the Sliding Window lesson page.
// 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 } - 3.Longest Repeating Character ReplacementMedium
A window is fixable if (length − count of its most common letter) ≤ k.
Expand right, count letters, track the max frequency in the window; while length − maxFreq > k shrink left. Answer is the largest window.
Target: O(n) time, O(26) space
Types such as ListNode, TreeNode and Node are the standard ones for these problems. Define them yourself if you run the code locally.
func characterReplacement(s string, k int) intTested with go test. Try it yourself first, then compare.
// CharacterReplacement: a window is fixable when (length - count of its most common letter) <= k. // maxFreq never needs to shrink: the window only grows when a new record frequency is set. func CharacterReplacement(s string, k int) int { var count [26]int best, maxFreq, left := 0, 0, 0 for right := 0; right < len(s); right++ { count[s[right]-'A']++ maxFreq = max(maxFreq, count[s[right]-'A']) for (right-left+1)-maxFreq > k { // more replacements needed than allowed: shrink count[s[left]-'A']-- left++ } best = max(best, right-left+1) } return best } - 4.Permutation in StringMedium
A permutation has the same letter counts. What size must the window always be?
Slide a fixed-size window (length of s1) over s2, maintaining 26 counts; compare with s1 counts (or track how many letters match).
Target: O(n) time, O(1) space
Types such as ListNode, TreeNode and Node are the standard ones for these problems. Define them yourself if you run the code locally.
func checkInclusion(s1 string, s2 string) boolTested with go test. Try it yourself first, then compare.
// CheckInclusion: s2 contains a permutation of s1 when some window of len(s1) has the same letter counts. func CheckInclusion(s1, s2 string) bool { if len(s1) > len(s2) { return false } var need, have [26]int for i := 0; i < len(s1); i++ { need[s1[i]-'a']++ have[s2[i]-'a']++ } if need == have { return true } for i := len(s1); i < len(s2); i++ { have[s2[i]-'a']++ // letter enters on the right have[s2[i-len(s1)]-'a']-- // letter leaves on the left if need == have { return true } } return false } - 5.Minimum Window SubstringHard
Track how many required letters are still missing. The window is valid at exactly zero missing.
Expand right until the window covers t; then shrink left as far as it stays valid, recording the smallest window each time.
Target: O(n + m) time
Types such as ListNode, TreeNode and Node are the standard ones for these problems. Define them yourself if you run the code locally.
func minWindow(s string, t string) stringTested with go test. Try it yourself first, then compare. It is explained step by step on the Sliding Window lesson page.
// 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] } - 6.Sliding Window MaximumHard
When a new number arrives, which numbers in the window can never be the maximum again?
Keep a deque of indices with decreasing values: pop from the back while smaller than the new value, pop from the front when it leaves the window. The front is the max.
Target: O(n) time, O(k) space
Types such as ListNode, TreeNode and Node are the standard ones for these problems. Define them yourself if you run the code locally.
func maxSlidingWindow(nums []int, k int) []intTested with go test. Try it yourself first, then compare.
// MaxSlidingWindow: keep a deque of indexes whose values decrease from front to back. // A smaller value behind a bigger newcomer can never be the maximum again, so it is dropped. func MaxSlidingWindow(nums []int, k int) []int { var dq, out []int for i, v := range nums { for len(dq) > 0 && nums[dq[len(dq)-1]] <= v { dq = dq[:len(dq)-1] // drop smaller values from the back } dq = append(dq, i) if dq[0] <= i-k { dq = dq[1:] // the front index slid out of the window } if i >= k-1 { out = append(out, nums[dq[0]]) } } return out }