Sliding Window in Java
Fixed and variable windows, the shrink condition that decides which you have, and why substring inside a loop turns an O(n) algorithm back into O(n squared).
A sliding window turns “check every subarray” into “adjust the one you have”. The pattern is short; the mistakes are in the shrink condition and in Java’s string copying.
Fixed window: add one, drop one
import java.util.*;
public class FixedWindow {
static int bruteMaxSum(int[] nums, int k) {
int best = Integer.MIN_VALUE;
for (int i = 0; i + k <= nums.length; i++) {
int sum = 0;
for (int j = i; j < i + k; j++) sum += nums[j]; // re-adds k elements
best = Math.max(best, sum);
}
return best;
}
static int windowMaxSum(int[] nums, int k) {
int sum = 0;
for (int i = 0; i < k; i++) sum += nums[i];
int best = sum;
for (int i = k; i < nums.length; i++) {
sum += nums[i] - nums[i - k]; // one add, one subtract
best = Math.max(best, sum);
}
return best;
}
public static void main(String[] args) {
int[] nums = new Random(3).ints(200_000, -100, 100).toArray();
int k = 1_000;
long t0 = System.nanoTime();
int a = bruteMaxSum(nums, k);
long t1 = System.nanoTime();
int b = windowMaxSum(nums, k);
long t2 = System.nanoTime();
System.out.printf("brute O(n*k) %8.2f ms %d%n", (t1-t0)/1e6, a);
System.out.printf("window O(n) %8.2f ms %d%n", (t2-t1)/1e6, b);
System.out.printf("speedup: %.0fx%n", (double)(t1-t0)/(t2-t1));
}
}$ java FixedWindow.java
brute O(n*k) 186.31 ms 8143
window O(n) 0.31 ms 8143
speedup: 601xsum += nums[i] - nums[i - k] is the whole idea: consecutive windows overlap in k-1 elements,
so recomputing them is waste. Same answer, 601 times less work.
The two edges to check: k > nums.length and k == 0. Decide what each should return — an
exception, or a sentinel — and say so.
Variable window: grow always, shrink while invalid
import java.util.*;
public class LongestUnique {
static int lengthOfLongestSubstring(String s) {
int[] lastSeen = new int[128];
Arrays.fill(lastSeen, -1);
int best = 0, left = 0;
for (int right = 0; right < s.length(); right++) {
char c = s.charAt(right);
if (lastSeen[c] >= left) left = lastSeen[c] + 1; // jump past the duplicate
lastSeen[c] = right;
best = Math.max(best, right - left + 1);
}
return best;
}
public static void main(String[] args) {
for (String s : new String[]{"abcabcbb", "bbbbb", "pwwkew", "", "au", "dvdf"})
System.out.printf("%-10s -> %d%n", "\"" + s + "\"", lengthOfLongestSubstring(s));
}
}$ java LongestUnique.java
"abcabcbb" -> 3
"bbbbb" -> 1
"pwwkew" -> 3
"" -> 0
"au" -> 2
"dvdf" -> 3"dvdf" is the case that catches naive versions. When the second d arrives, lastSeen['d']
is 0 — but if left has already moved past 0, jumping back would grow the window
incorrectly. The lastSeen[c] >= left guard is what prevents it, and "dvdf" -> 3 is the test
that proves the guard is there.
The Java-specific trap: substring inside the loop
public class SubstringCost {
static String slow(String s) {
String best = "";
for (int left = 0; left < s.length(); left++) {
boolean[] seen = new boolean[128];
int right = left;
while (right < s.length() && !seen[s.charAt(right)]) seen[s.charAt(right++)] = true;
String candidate = s.substring(left, right); // O(k) copy every time
if (candidate.length() > best.length()) best = candidate;
}
return best;
}
static String fast(String s) {
int[] lastSeen = new int[128];
java.util.Arrays.fill(lastSeen, -1);
int bestStart = 0, bestLen = 0, left = 0;
for (int right = 0; right < s.length(); right++) {
char c = s.charAt(right);
if (lastSeen[c] >= left) left = lastSeen[c] + 1;
lastSeen[c] = right;
if (right - left + 1 > bestLen) { bestLen = right - left + 1; bestStart = left; }
}
return s.substring(bestStart, bestStart + bestLen); // one copy, at the end
}
public static void main(String[] args) {
StringBuilder sb = new StringBuilder();
java.util.Random rnd = new java.util.Random(11);
for (int i = 0; i < 60_000; i++) sb.append((char)(97 + rnd.nextInt(8)));
String s = sb.toString();
long t0 = System.nanoTime();
String a = slow(s);
long t1 = System.nanoTime();
String b = fast(s);
long t2 = System.nanoTime();
System.out.printf("substring in loop %8.2f ms len %d%n", (t1-t0)/1e6, a.length());
System.out.printf("indices, one copy %8.2f ms len %d%n", (t2-t1)/1e6, b.length());
System.out.printf("ratio: %.0fx same answer: %s%n", (double)(t1-t0)/(t2-t1), a.equals(b));
}
}$ java SubstringCost.java
substring in loop 714.06 ms len 8
indices, one copy 1.42 ms len 8
ratio: 503x same answer: trueBefore Java 7, substring shared the parent’s char[] and was O(1) — which also leaked the
whole parent string when you kept a small slice. The fix in Java 7 made it copy, which removed
the leak and made it O(k).
“
substringcopies since Java 7, so calling it per window makes the scan O(n·k). I track the best start and length as ints and callsubstringonce at the end. The same reasoning applies to building strings with+=in a loop.”
Note that slow here is also O(n·k) in its scanning, so the 503x combines both effects — worth
saying rather than attributing all of it to substring.
The variable-window template
import java.util.*;
public class MinSubarray {
static int minSubArrayLen(int target, int[] nums) {
int left = 0, sum = 0, best = Integer.MAX_VALUE;
for (int right = 0; right < nums.length; right++) {
sum += nums[right]; // 1. grow
while (sum >= target) { // 2. shrink WHILE valid (minimising)
best = Math.min(best, right - left + 1);
sum -= nums[left++];
}
}
return best == Integer.MAX_VALUE ? 0 : best;
}
public static void main(String[] args) {
System.out.println(minSubArrayLen(7, new int[]{2,3,1,2,4,3}));
System.out.println(minSubArrayLen(11, new int[]{1,1,1,1,1,1,1,1}));
System.out.println(minSubArrayLen(4, new int[]{1,4,4}));
}
}$ java MinSubarray.java
2
0
1Compare the two shrink conditions side by side — this is the distinction people get backwards:
MAXIMISING (longest valid window) MINIMISING (shortest valid window)
grow right grow right
while (INVALID) shrink left while (VALID) record, then shrink left
record after the while record inside the whileGetting these the wrong way round produces code that looks right and returns the wrong number on half the cases. Writing the shrink condition first, before the body, avoids it.
Why this is still O(n): left only moves forward and never passes right, so across the
whole run it advances at most n times. The inner while does not multiply the outer loop — the
total is bounded by 2n.
Character frequency windows
import java.util.*;
public class Permutation {
static boolean containsPermutation(String pattern, String text) {
if (pattern.length() > text.length()) return false;
int[] need = new int[26], have = new int[26];
for (char c : pattern.toCharArray()) need[c - 97]++;
int k = pattern.length();
for (int i = 0; i < text.length(); i++) {
have[text.charAt(i) - 97]++;
if (i >= k) have[text.charAt(i - k) - 97]--; // drop the element leaving
if (i >= k - 1 && Arrays.equals(need, have)) return true;
}
return false;
}
public static void main(String[] args) {
System.out.println(containsPermutation("ab", "eidbaooo"));
System.out.println(containsPermutation("ab", "eidboaoo"));
System.out.println(containsPermutation("abc", "ab"));
}
}$ java Permutation.java
true
false
falseArrays.equals on two 26-element arrays is O(26) — a constant, so the whole scan stays O(n).
Mentioning that explicitly is the difference between “it’s O(n)” and “it’s O(26n), which is
O(n)”. A tighter version tracks a matches counter and updates it in O(1) per step; say it
exists, and only write it if asked.
Recognising it
SIGNAL WINDOW
"subarray of size k", "every window of k" fixed
"maximum average of k consecutive" fixed
"longest substring with at most k distinct" variable, shrink while > k
"longest with no repeats" variable, jump left past the duplicate
"smallest subarray with sum >= S" variable, shrink while valid
"permutation / anagram in a string" fixed, frequency arrays
contiguous + optimise a length almost always a window
NOT contiguous (subsequence, any order) not a window — usually DP or sortingThat last line saves time. “Subarray” and “substring” are contiguous; “subsequence” is not, and a window cannot solve it.
Edge cases
public class Edges {
public static void main(String[] args) {
System.out.println(LongestUnique.lengthOfLongestSubstring(""));
System.out.println(LongestUnique.lengthOfLongestSubstring("a"));
System.out.println(MinSubarray.minSubArrayLen(100, new int[]{1,2,3}));
System.out.println(MinSubarray.minSubArrayLen(1, new int[]{}));
}
}0
1
0
0Empty input, single element, and “no window satisfies the condition” are the three. The last one
is why best starts at Integer.MAX_VALUE and is translated to 0 on the way out — returning
MAX_VALUE to a caller is a bug that survives most sample tests.
Practice
1. Time the brute-force k-window sum against the rolling sum.
brute O(n*k) 186.31 ms window O(n) 0.31 ms 601xConsecutive windows share k-1 elements. sum += nums[i] - nums[i-k] is one add and one
subtract instead of k additions.
2. Call substring once per window, then once at the end.
substring in loop 714.06 ms indices, one copy 1.42 mssubstring copies since Java 7 — O(k), not O(1). Track bestStart and bestLen as ints and
materialise the string once.
3. Run the longest-unique-substring solver on "dvdf".
"dvdf" -> 3If it returns 2, the lastSeen[c] >= left guard is missing and left is jumping backwards.
This is the standard test for that specific bug.
4. Swap the shrink condition between maximising and minimising.
maximise: while (INVALID) shrink; record after
minimise: while (VALID) record, then shrinkReversed, the code still compiles and still returns a plausible number. Write the shrink condition before the body.
Next: stacks and monotonic stacks — ArrayDeque over the legacy Stack, and the amortised
argument for why one pass suffices.