Sliding Window

Overview

Sliding window algorithms process contiguous ranges without recomputing every range from scratch. Two indices describe the current window, while a small amount of state—such as a sum, product, frequency map, or distinct count—is updated as elements enter and leave.

Use a fixed-size window when every candidate range has the same length. Use a variable-size window when the right boundary expands until a constraint fails and the left boundary advances until the window becomes valid again. Most solutions run in O(n) time because each element enters and leaves the window at most once.

Templates

  • Fixed-size window

    • Add values[right] to the window state.
    • If windowSize > k, remove values[left] and increment left.
    • If windowSize == k, evaluate the current candidate.

  • Variable-size window

    • For each right, add values[right] to the state.
    • While windowIsInvalid, remove values[left] and increment left.
    • Once valid, update the answer using [left, right].
    • The validity rule must be restored before moving right again.

Fixed-length sliding window

public static int fixedLengthSlidingWindow(int[] nums, int k) {
    int state = 0; // choose appropriate data structure
    int start = 0;
    int max = 0;

    for (int end = 0; end < nums.length; end++) {
        // extend window
        // add nums[end] to state in O(1) time
        if (end - start + 1 == k) {
            // INVARIANT: size of the window is k here.
            max = Math.max(max, state); // replace state as appropriate
            // contract window
            // remove nums[start] from state in O(1) time
            start++;
        }
    }

    return max;
}

Variable-size sliding window

import java.util.HashMap;
import java.util.Map;

public static int variableLengthSlidingWindow(int[] nums) {
    Map<Integer, Integer> state = new HashMap<>(); // choose appropriate data structure
    int start = 0;
    int max = 0;

    for (int end = 0; end < nums.length; end++) {
        // extend window
        // add nums[end] to state in O(1) time
        while (!isValid(state)) {
            // repeatedly contract window until it is valid again
            // remove nums[start] from state in O(1) time
            start++;
        }
        // INVARIANT: state of current window is valid here.
        max = Math.max(max, end - start + 1);
    }

    return max;
}

Problems

3. Longest Substring Without Repeating Characters

Find the longest substring containing no repeated character. The Java solution stores each character’s most recent index and jumps left past a duplicate in one step. The Python solution counts characters and shrinks the window until the duplicate is removed. Both approaches run in O(n) time.

import java.util.HashMap;
import java.util.Map;

class Solution {
	public int lengthOfLongestSubstring(String s) {
		Map<Character, Integer> lastSeen = new HashMap<>();
		int left = 0;
		int best = 0;

		for (int right = 0; right < s.length(); right++) {
			char current = s.charAt(right);

			if (lastSeen.containsKey(current)) {
				left = Math.max(left, lastSeen.get(current) + 1);
			}

			lastSeen.put(current, right);
			best = Math.max(best, right - left + 1);
		}

		return best;
	}
}

424. Longest Repeating Character Replacement

Return the longest substring that can be made uniform by replacing at most k characters. A window is valid when window length - highest frequency <= k. The Python solution recomputes the highest frequency from a fixed-size array, while the Java solution stores counts in a map and safely caches the largest frequency seen while expanding the window.

import java.util.HashMap;
import java.util.Map;

class Solution {
    public int characterReplacement(String s, int k) {
        Map<Character, Integer> freq = new HashMap<>();
        int res = 0;
        int start = 0;
        int maxCount = 0; // count of the most frequent char in the window

        for (int end = 0; end < s.length(); end++) {
            char c = s.charAt(end);
            freq.put(c, freq.getOrDefault(c, 0) + 1);

            maxCount = Math.max(maxCount, freq.get(c));

            while (end - start + 1 - maxCount > k) {
                char startChar = s.charAt(start);
                freq.put(startChar, freq.get(startChar)-1);
                start++;
            }

            res = Math.max(res, end - start + 1);
        }

        return res;
    }
}

567. Permutation in String

Determine whether s2 contains a permutation of s1. Maintain a fixed-size window equal to s1.length() and compare its character counts with the required counts. Python uses Counter objects, while Java uses two arrays for the 26 lowercase letters. Both approaches run in O(n) time.

import java.util.Arrays;

class Solution {
	public boolean checkInclusion(String s1, String s2) {
		if (s1.length() > s2.length()) {
			return false;
		}

		int[] required = new int[26];
		int[] window = new int[26];

		for (int i = 0; i < s1.length(); i++) {
			required[s1.charAt(i) - 'a']++;
			window[s2.charAt(i) - 'a']++;
		}

		if (Arrays.equals(required, window)) {
			return true;
		}

		for (int right = s1.length(); right < s2.length(); right++) {
			window[s2.charAt(right) - 'a']++;
			window[s2.charAt(right - s1.length()) - 'a']--;

			if (Arrays.equals(required, window)) {
				return true;
			}
		}

		return false;
	}
}

713. Subarray Product Less Than K

Count contiguous subarrays whose product is smaller than k. Because all values are positive, expanding the window can only increase the product; shrink until it is valid, then every subarray ending at right and starting between left and right is valid.

class Solution {
    public int numSubarrayProductLessThanK(int[] nums, int k) {
        int res = 0;
        int prod = 1;
        int left = 0;

        for (int right = 0; right < nums.length; right++){
            prod = prod * nums[right];
            while (left <= right && prod >= k){
                prod = prod / nums[left];
                left += 1;
            }
            res += (right-left+1);
        }

        return res;
    }
}

2461. Maximum Sum of Distinct Subarrays With Length K

Find the maximum sum among length-k subarrays whose elements are all distinct. Maintain the window sum and a frequency map; after removing excess elements, evaluate the sum only when the window has size k and the map also contains k keys.

import java.util.HashMap;
import java.util.Map;

class Solution {
	public long maximumSubarraySum(int[] nums, int k) {
		Map<Integer, Integer> counts = new HashMap<>();
		long sum = 0;
		long best = 0;
		int left = 0;

		for (int right = 0; right < nums.length; right++) {
			counts.merge(nums[right], 1, Integer::sum);
			sum += nums[right];

			if (right - left + 1 > k) {
				int removed = nums[left++];
				sum -= removed;
				counts.compute(removed, (key, count) ->
					count == 1 ? null : count - 1
				);
			}

			if (right - left + 1 == k && counts.size() == k) {
				best = Math.max(best, sum);
			}
		}

		return best;
	}
}