Chapter 4
Sliding Window in Java
Java Data Structures & Algorithms Series
The Sliding Window technique maintains a subset of elements (a 'window') over a sequence and
slides it forward, avoiding redundant recomputation. It converts many O(n²) brute-force solutions
into clean O(n) solutions.
1 The Core Idea
Instead of recomputing a subarray's property from scratch each time, you add the new right
element and remove the old left element as the window slides.
Array: [2, 1, 5, 1, 3, 2], k=3
Brute Force — O(n²): Sliding Window — O(n):
sum(0..2) = 8 window = [2,1,5] sum=8
sum(1..3) = 7 ← recompute slide → remove 2, add 1 → sum=7
sum(2..4) = 9 ← recompute slide → remove 1, add 3 → sum=9
sum(3..5) = 6 ← recompute slide → remove 5, add 2 → sum=6
2 Two Types of Sliding Window
Type Window Size How to Shrink
Fixed Size Always exactly K Slide by removing arr[left] every
step
Variable Size Grows & shrinks Shrink left when window
becomes invalid
3 Fixed Window — Pattern 1: Max Sum Subarray of Size K
Problem: Find maximum sum of any contiguous subarray of size K.
arr = [2, 1, 5, 1, 3, 2], k=3
Windows: [2,1,5]=8, [1,5,1]=7, [5,1,3]=9, [1,3,2]=6
Answer: 9
public static int maxSumSubarray(int[] arr, int k) {
int n = [Link];
if (n < k) return -1;
// Build first window
int windowSum = 0;
for (int i = 0; i < k; i++) windowSum += arr[i];
int maxSum = windowSum;
// Slide: add right element, remove left element
for (int right = k; right < n; right++) {
windowSum += arr[right]; // add new right element
windowSum -= arr[right - k]; // remove old left element
maxSum = [Link](maxSum, windowSum);
}
return maxSum;
}
// Time: O(n) | Space: O(1)
Trace walkthrough:
arr=[2,1,5,1,3,2], k=3
Initial window: 2+1+5 = 8, maxSum=8
right=3: +1-2 = 7, maxSum=8
right=4: +3-1 = 9, maxSum=9 ✅
right=5: +2-5 = 6, maxSum=9
4 Fixed Window — Pattern 2: First Negative in Every Window of Size K
public static List<Integer> firstNegative(int[] arr, int k) {
List<Integer> result = new ArrayList<>();
Deque<Integer> negatives = new ArrayDeque<>(); // stores indices of negatives
for (int right = 0; right < [Link]; right++) {
if (arr[right] < 0) [Link](right);
// Remove elements outside current window from front
if (![Link]() && [Link]() < right - k + 1)
[Link]();
// Window is complete — record first negative
if (right >= k - 1)
[Link]([Link]() ? 0 : arr[[Link]()]);
}
return result;
}
// Time: O(n) | Space: O(k)
Example:
arr=[12,-1,-7,8,-15,30,16,28], k=3
Window [-1,-7,8] → -1
Window [-7,8,-15] → -7
Window [8,-15,30] → -15
Window [-15,30,16] → -15
Window [30,16,28] → 0 (no negative)
5 Fixed Window — Pattern 3: Count Anagrams of Pattern in String
public static int countAnagrams(String s, String p) {
if ([Link]() < [Link]()) return 0;
int[] pCount = new int[26];
int[] wCount = new int[26];
for (char c : [Link]()) pCount[c - 'a']++;
for (int i = 0; i < [Link](); i++) wCount[[Link](i) - 'a']++;
int count = [Link](pCount, wCount) ? 1 : 0;
for (int right = [Link](); right < [Link](); right++) {
wCount[[Link](right) - 'a']++; // add new right char
wCount[[Link](right - [Link]()) - 'a']--; // remove old left char
if ([Link](pCount, wCount)) count++;
}
return count;
}
// Time: O(n × 26) ≈ O(n) | Space: O(1)
6 Variable Window — Pattern 4: Longest Substring Without Repeating Characters
Problem: Find length of longest substring with all unique characters.
s = "abcabcbb"
Windows: "abc"=3, then a repeats → shrink → "bca"=3
Answer: 3
public static int lengthOfLongestSubstring(String s) {
Map<Character, Integer> lastSeen = new HashMap<>();
int maxLen = 0, left = 0;
for (int right = 0; right < [Link](); right++) {
char c = [Link](right);
// If char was seen inside current window, shrink from left
if ([Link](c) && [Link](c) >= left)
left = [Link](c) + 1; // jump left past the duplicate
[Link](c, right);
maxLen = [Link](maxLen, right - left + 1);
}
return maxLen;
}
// Time: O(n) | Space: O(min(n, alphabet))
Trace walkthrough:
s = "abcabcbb"
right=0(a): left=0, window="a", len=1
right=1(b): left=0, window="ab", len=2
right=2(c): left=0, window="abc", len=3
right=3(a): a seen at 0 → left=1, window="bca", len=3
right=4(b): b seen at 1 → left=2, window="cab", len=3
right=5(c): c seen at 2 → left=3, window="abc", len=3
right=6(b): b seen at 4 → left=5, window="cb", len=2
right=7(b): b seen at 6 → left=7, window="b", len=1
Answer: 3 ✅
7 Variable Window — Pattern 5: Longest Substring with At Most K Distinct
Characters
public static int longestKDistinct(String s, int k) {
Map<Character, Integer> freq = new HashMap<>();
int maxLen = 0, left = 0;
for (int right = 0; right < [Link](); right++) {
[Link]([Link](right), 1, Integer::sum);
// Shrink until we have at most k distinct chars
while ([Link]() > k) {
char lc = [Link](left);
[Link](lc, -1, Integer::sum);
if ([Link](lc) == 0) [Link](lc);
left++;
}
maxLen = [Link](maxLen, right - left + 1);
}
return maxLen;
}
// Time: O(n) | Space: O(k)
Trace — s="araaci", k=2:
right=0(a): {a:1}, len=1
right=1(r): {a:1,r:1}, len=2
right=2(a): {a:2,r:1}, len=3
right=3(a): {a:3,r:1}, len=4
right=4(c): {a:3,r:1,c:1} size=3>2 → shrink
remove a → {a:2,r:1,c:1} still 3 → shrink
remove r → {a:2,c:1} size=2, left=2, len=3
right=5(i): {a:2,c:1,i:1} size=3>2 → shrink
remove a → {a:1,c:1,i:1} still 3 → shrink
remove a → {c:1,i:1} size=2, left=4, len=2
Answer: 4 ✅
8 Variable Window — Pattern 6: Minimum Size Subarray Sum ≥ Target
Problem: Find minimum length subarray whose sum ≥ target.
arr = [2,3,1,2,4,3], target = 7
Answer: 2 (subarray [4,3])
public static int minSubarrayLen(int target, int[] nums) {
int minLen = Integer.MAX_VALUE;
int windowSum = 0, left = 0;
for (int right = 0; right < [Link]; right++) {
windowSum += nums[right]; // expand window
// Shrink from left while sum is still >= target
while (windowSum >= target) {
minLen = [Link](minLen, right - left + 1);
windowSum -= nums[left];
left++;
}
}
return minLen == Integer.MAX_VALUE ? 0 : minLen;
}
// Time: O(n) | Space: O(1)
Trace walkthrough:
arr=[2,3,1,2,4,3], target=7
right=0: sum=2 <7
right=1: sum=5 <7
right=2: sum=6 <7
right=3: sum=8 ≥7 → minLen=4, remove 2 → sum=6, left=1
right=4: sum=10 ≥7 → minLen=4, remove 3 → sum=7, left=2
sum=7 ≥7 → minLen=3, remove 1 → sum=6, left=3
right=5: sum=9 ≥7 → minLen=3, remove 2 → sum=7, left=4
sum=7 ≥7 → minLen=2, remove 4 → sum=3, left=5
Answer: 2 ✅
9 Variable Window — Pattern 7: Longest Repeating Character Replacement
Problem: Replace at most K characters to get the longest all-same-character substring.
s="AABABBA", k=1
Answer: 4 (replace one B in "AABA" → "AAAA")
⭐ Key Insight: Window is valid when → windowSize - maxFreqChar ≤ k
public static int characterReplacement(String s, int k) {
int[] freq = new int[26];
int maxFreq = 0, maxLen = 0, left = 0;
for (int right = 0; right < [Link](); right++) {
freq[[Link](right) - 'A']++;
maxFreq = [Link](maxFreq, freq[[Link](right) - 'A']);
int windowSize = right - left + 1;
if (windowSize - maxFreq > k) { // need more replacements than k
freq[[Link](left) - 'A']--;
left++;
}
maxLen = [Link](maxLen, right - left + 1);
}
return maxLen;
}
// Time: O(n) | Space: O(26) = O(1)
10 Variable Window — Pattern 8: Permutation in String
Problem: Check if any permutation of p exists as a substring of s.
s = "eidbaooo", p = "ab"
Answer: true ("ba" is a permutation of "ab")
public static boolean checkInclusion(String p, String s) {
if ([Link]() > [Link]()) return false;
int[] pCount = new int[26];
int[] wCount = new int[26];
for (char c : [Link]()) pCount[c - 'a']++;
int k = [Link]();
for (int right = 0; right < [Link](); right++) {
wCount[[Link](right) - 'a']++;
if (right >= k)
wCount[[Link](right - k) - 'a']--; // fixed window: remove left
if ([Link](pCount, wCount)) return true;
}
return false;
}
// Time: O(n × 26) ≈ O(n) | Space: O(1)
11 Variable Window — Pattern 9: Binary Subarray with Sum
Problem: Count subarrays with sum equal to goal in a binary array.
⭐ Trick: count(sum == goal) = count(sum ≤ goal) − count(sum ≤ goal − 1)
public static int numSubarraysWithSum(int[] nums, int goal) {
return atMost(nums, goal) - atMost(nums, goal - 1);
}
private static int atMost(int[] nums, int goal) {
if (goal < 0) return 0;
int left = 0, sum = 0, count = 0;
for (int right = 0; right < [Link]; right++) {
sum += nums[right];
while (sum > goal) sum -= nums[left++];
count += right - left + 1; // all subarrays ending at right
}
return count;
}
// Time: O(n) | Space: O(1)
12 Decision Guide — Which Window Type?
Is window size FIXED (always K)?
YES → Fixed window (slide mechanically: add right, remove left)
NO → Variable window
Variable window — what makes it invalid?
Sum > target → shrink (minimum subarray sum)
Distinct chars > k → shrink (k distinct characters)
Duplicates exist → shrink (no repeating characters)
Replacements > k → shrink (character replacement)
Shrink condition is always a WHILE loop, never an IF.
13 Full Runnable Java Program
import [Link].*;
public class Chapter4SlidingWindow {
public static void main(String[] args) {
// Fixed Window
[Link]("Max Sum k=3: " +
maxSumSubarray(new int[]{2,1,5,1,3,2}, 3)); // 9
[Link]("First Negative k=3: " +
firstNegative(new int[]{12,-1,-7,8,-15,30,16,28}, 3)); // [-1,-
7,-15,-15,0]
[Link]("Count Anagrams: " +
countAnagrams("cbaebabacd", "abc")); // 2
// Variable Window
[Link]("Longest No Repeat: " +
lengthOfLongestSubstring("abcabcbb")); // 3
[Link]("Longest K=2 Distinct: " +
longestKDistinct("araaci", 2)); // 4
[Link]("Min Subarray Sum>=7: " +
minSubarrayLen(7, new int[]{2,3,1,2,4,3})); // 2
[Link]("Char Replacement k=1: " +
characterReplacement("AABABBA", 1)); // 4
[Link]("Permutation in String: " +
checkInclusion("ab", "eidbaooo")); // true
[Link]("Binary Subarray Sum=2: " +
numSubarraysWithSum(new int[]{1,0,1,0,1}, 2)); // 4
}
static int maxSumSubarray(int[] arr, int k) {
int sum = 0;
for (int i = 0; i < k; i++) sum += arr[i];
int max = sum;
for (int r = k; r < [Link]; r++) {
sum += arr[r] - arr[r - k];
max = [Link](max, sum);
}
return max;
}
static List<Integer> firstNegative(int[] arr, int k) {
List<Integer> res = new ArrayList<>();
Deque<Integer> dq = new ArrayDeque<>();
for (int r = 0; r < [Link]; r++) {
if (arr[r] < 0) [Link](r);
if (![Link]() && [Link]() < r - k + 1) [Link]();
if (r >= k - 1) [Link]([Link]() ? 0 : arr[[Link]()]);
}
return res;
}
static int countAnagrams(String s, String p) {
int[] pc = new int[26], wc = new int[26]; int cnt = 0;
for (char c : [Link]()) pc[c - 'a']++;
for (int i = 0; i < [Link](); i++) wc[[Link](i) - 'a']++;
if ([Link](pc, wc)) cnt++;
for (int r = [Link](); r < [Link](); r++) {
wc[[Link](r) - 'a']++;
wc[[Link](r - [Link]()) - 'a']--;
if ([Link](pc, wc)) cnt++;
}
return cnt;
}
static int lengthOfLongestSubstring(String s) {
Map<Character, Integer> map = new HashMap<>(); int max = 0, l = 0;
for (int r = 0; r < [Link](); r++) {
char c = [Link](r);
if ([Link](c) && [Link](c) >= l) l = [Link](c) + 1;
[Link](c, r); max = [Link](max, r - l + 1);
}
return max;
}
static int longestKDistinct(String s, int k) {
Map<Character, Integer> freq = new HashMap<>(); int max = 0, l = 0;
for (int r = 0; r < [Link](); r++) {
[Link]([Link](r), 1, Integer::sum);
while ([Link]() > k) {
char lc = [Link](l);
[Link](lc, -1, Integer::sum);
if ([Link](lc) == 0) [Link](lc);
l++;
}
max = [Link](max, r - l + 1);
}
return max;
}
static int minSubarrayLen(int target, int[] nums) {
int min = Integer.MAX_VALUE, sum = 0, l = 0;
for (int r = 0; r < [Link]; r++) {
sum += nums[r];
while (sum >= target) { min = [Link](min, r - l + 1); sum -= nums[l+
+]; }
}
return min == Integer.MAX_VALUE ? 0 : min;
}
static int characterReplacement(String s, int k) {
int[] freq = new int[26]; int maxF = 0, max = 0, l = 0;
for (int r = 0; r < [Link](); r++) {
freq[[Link](r) - 'A']++;
maxF = [Link](maxF, freq[[Link](r) - 'A']);
if (r - l + 1 - maxF > k) freq[[Link](l++) - 'A']--;
max = [Link](max, r - l + 1);
}
return max;
}
static boolean checkInclusion(String p, String s) {
int[] pc = new int[26], wc = new int[26]; int k = [Link]();
for (char c : [Link]()) pc[c - 'a']++;
for (int r = 0; r < [Link](); r++) {
wc[[Link](r) - 'a']++;
if (r >= k) wc[[Link](r - k) - 'a']--;
if ([Link](pc, wc)) return true;
}
return false;
}
static int numSubarraysWithSum(int[] nums, int goal) {
return atMost(nums, goal) - atMost(nums, goal - 1);
}
static int atMost(int[] nums, int goal) {
if (goal < 0) return 0; int l = 0, sum = 0, cnt = 0;
for (int r = 0; r < [Link]; r++) {
sum += nums[r];
while (sum > goal) sum -= nums[l++];
cnt += r - l + 1;
}
return cnt;
}
}
14 Practice Problems for Chapter 4
Solve in this order:
Difficulty Problem
Easy Maximum average subarray of size K (LeetCode
#643)
Easy Contains duplicate II — within K distance (LeetCode
#219)
Medium Longest substring without repeating chars
(LeetCode #3)
Medium Permutation in string (LeetCode #567)
Medium Longest repeating character replacement (LeetCode
#424)
Medium Minimum size subarray sum (LeetCode #209)
Medium Fruit into baskets — at most 2 distinct (LeetCode
#904)
Medium Subarray product less than K (LeetCode #713)
Hard Minimum window substring (LeetCode #76)
Hard Sliding window maximum — deque (LeetCode
#239)
💡 Key Insight: Two rules that separate good solutions from great ones:
1. The shrink condition is always a WHILE loop, never an IF — keep shrinking until the window is
valid again, not just once.
2. Fixed windows are a special case of variable windows where you enforce exactly K size. Master
these two templates and every sliding window problem becomes recognizable.
Next up is Chapter 5 — Hashing! 🚀