Sliding window is the go-to pattern for subarray and substring problems. Here's the fixed-size and variable-size templates, plus the counter trick that solves 'at most K' problems.
Sliding window replaces O(n²) brute force with O(n) for problems involving contiguous subarrays or substrings. There are two variants — fixed size and variable size — and once you have both templates, you can solve most problems in 15 minutes.
1// Maximum sum of subarray of size k
2public int maxSumSubarray(int[] nums, int k) {
3 int windowSum = 0;
4 for (int i = 0; i < k; i++) windowSum += nums[i];
5
6 int maxSum = windowSum;
7 for (int i = k; i < nums.length; i++) {
8 windowSum += nums[i] - nums[i - k]; // slide: add right, remove left
9 maxSum = Math.max(maxSum, windowSum);
10 }
11 return maxSum;
12}1// Longest substring with at most K distinct characters
2public int lengthOfLongestSubstringKDistinct(String s, int k) {
3 Map<Character, Integer> freq = new HashMap<>();
4 int left = 0, maxLen = 0;
5
6 for (int right = 0; right < s.length(); right++) {
7 char c = s.charAt(right);
8 freq.merge(c, 1, Integer::sum);
9
10 // Shrink window until constraint is satisfied
11 while (freq.size() > k) {
12 char leftChar = s.charAt(left++);
13 freq.merge(leftChar, -1, Integer::sum);
14 if (freq.get(leftChar) == 0) freq.remove(leftChar);
15 }
16
17 maxLen = Math.max(maxLen, right - left + 1);
18 }
19 return maxLen;
20}The 'at most K' trick: problems asking for exactly K can be solved as atMost(K) - atMost(K-1). This converts a hard exact-count problem into two easy sliding window passes.
The hardest sliding window variant. Use two frequency maps — one for the target chars needed, one for the current window — and a 'formed' counter that tracks how many chars meet their required frequency.
1public String minWindow(String s, String t) {
2 Map<Character, Integer> need = new HashMap<>();
3 for (char c : t.toCharArray()) need.merge(c, 1, Integer::sum);
4
5 int left = 0, formed = 0, required = need.size();
6 int[] ans = {-1, 0, 0}; // length, left, right
7 Map<Character, Integer> window = new HashMap<>();
8
9 for (int right = 0; right < s.length(); right++) {
10 char c = s.charAt(right);
11 window.merge(c, 1, Integer::sum);
12 if (need.containsKey(c) && window.get(c).equals(need.get(c))) formed++;
13
14 while (formed == required) {
15 if (ans[0] == -1 || right - left + 1 < ans[0])
16 ans = new int[]{right - left + 1, left, right};
17 char lc = s.charAt(left++);
18 window.merge(lc, -1, Integer::sum);
19 if (need.containsKey(lc) && window.get(lc) < need.get(lc)) formed--;
20 }
21 }
22 return ans[0] == -1 ? "" : s.substring(ans[1], ans[2] + 1);
23}This problem teaches the key insight of variable windows: you don't always need to shrink when the window becomes invalid — just stop growing it. The window size represents the best answer seen so far.
1// You can replace at most k characters — find the longest valid window
2public int characterReplacement(String s, int k) {
3 int[] freq = new int[26];
4 int left = 0, maxFreq = 0, result = 0;
5
6 for (int right = 0; right < s.length(); right++) {
7 freq[s.charAt(right) - 'A']++;
8 maxFreq = Math.max(maxFreq, freq[s.charAt(right) - 'A']);
9
10 // windowSize - maxFreq = chars we need to replace
11 int windowSize = right - left + 1;
12 if (windowSize - maxFreq > k) {
13 freq[s.charAt(left) - 'A']--;
14 left++;
15 }
16 result = Math.max(result, right - left + 1);
17 }
18 return result;
19}1// Max of every window of size k using monotonic deque — O(n)
2public int[] maxSlidingWindow(int[] nums, int k) {
3 int[] result = new int[nums.length - k + 1];
4 Deque<Integer> deque = new ArrayDeque<>(); // stores indices
5
6 for (int i = 0; i < nums.length; i++) {
7 // Remove elements outside the window
8 while (!deque.isEmpty() && deque.peekFirst() < i - k + 1)
9 deque.pollFirst();
10 // Maintain decreasing order — remove smaller elements from back
11 while (!deque.isEmpty() && nums[deque.peekLast()] < nums[i])
12 deque.pollLast();
13 deque.offerLast(i);
14 if (i >= k - 1) result[i - k + 1] = nums[deque.peekFirst()];
15 }
16 return result;
17}Sliding Window Maximum is really a monotonic deque problem disguised as a sliding window. The deque maintains indices of potentially useful maximums — whenever a new element is larger than the back, pop the back (it can never be the max for any future window).
More in DSA