Sliding Window

Algorithm Summary

A sliding window solves contiguous subarray, substring, and linked-segment problems by turning many nested-loop searches into a single pass. It is a strong signal when the input is contiguous and the goal mentions a minimum, maximum, longest, or shortest range.

The reusable rhythm is enter, leave, calculate:

1. Move right and add the new value to the window.
2. While the window is invalid, remove values from left.
3. Calculate the answer from the now-valid window.

Map<Character, Integer> counts = new HashMap<>();
int left = 0;
int answer = 0;

for (int right = 0; right < s.length(); right++) {
    char incoming = s.charAt(right);
    counts.put(incoming, counts.getOrDefault(incoming, 0) + 1);

    while (counts.size() > k) {
        char outgoing = s.charAt(left++);
        counts.put(outgoing, counts.get(outgoing) - 1);
        if (counts.get(outgoing) == 0) counts.remove(outgoing);
    }
    answer = Math.max(answer, right - left + 1);
}

Examples

Longest Substring Without Repeating Characters — LC 3

Count each character in the window. If the incoming character appears more than once, shrink from the left until it is unique again, then update the maximum width.

Longest Substring with At Most K Distinct Characters — LC 340

Track character counts in a map. The window is valid while the map contains at most k keys.

Minimum Window Substring — LC 76

Track how many required characters from t are currently satisfied. Once all are present, repeatedly shrink the left edge and record the smallest valid range. Store the best starting position so the substring can be returned, not just its length.

if (windowLength < minLength) {
    minLength = windowLength;
    minStart = left;
}

Minimum Size Subarray Sum — LC 209

For a positive array, add values until the sum reaches target, then remove from the left while the target is still satisfied. Every valid shrink is a chance to improve the minimum length.

int left = 0;
int sum = 0;
int result = Integer.MAX_VALUE;

for (int right = 0; right < nums.length; right++) {
    sum += nums[right];
    while (sum >= target) {
        result = Math.min(result, right - left + 1);
        sum -= nums[left++];
    }
}
return result == Integer.MAX_VALUE ? 0 : result;