// Sliding Window

core idea

A window [left, right] slides over contiguous data. right only ever moves forward, adding one element to the window each step; left only ever moves forward too, removing elements when some rule says the window should shrink. Because every index enters the window exactly once and leaves at most once, the whole scan is O(n) — no re-scanning a subarray from scratch the way a brute force does. There are two shapes — fixed and variable — and the variable shape splits by shrink discipline:

when to reach for it

• The question is about a contiguous run — subarray or substring, not any subsequence.
• Keywords: “substring”, “subarray”, “size k”, “at most/exactly k distinct”, “minimum/shortest window containing”.
• A brute force would recompute a sum, count, or set from scratch for every start index — O(n·k) or worse — when the window’s state can instead be updated incrementally as one element enters and one leaves.
• Fixed-size window: every slide adds one element and removes one. Variable-size window: right always advances; left catches up under a validity rule.

universal templates

Fixed window — size never changes, so there’s no validity check, only bookkeeping:

public int FixedWindow(int[] nums, int k)
{
    int windowSum = 0;
    for (int i = 0; i < k; i++) windowSum += nums[i];   // seed the first window once

    int best = windowSum;
    for (int right = k; right < nums.Length; right++)
    {
        int left = right - k;
        windowSum += nums[right] - nums[left];          // add entering, remove leaving — O(1) per slide
        best = Math.Max(best, windowSum);
    }
    return best;
}

Variable window, longest — grow greedily, only shrink when forced:

public int VariableWindowLongest(/* input */)
{
    // window state lives here: HashSet<char>, Dictionary<char,int>, int[] freq — whatever Valid() needs
    int left = 0, best = 0;

    for (int right = 0; right < n; right++)
    {
        Add(right);                       // window always grows by one element

        while (!IsValid())                // longest → shrink while INVALID
        {
            Remove(left);
            left++;
        }
        best = Math.Max(best, right - left + 1);
    }
    return best;
}

Variable window, shortest — shrink eagerly, record on the way down:

public int VariableWindowShortest(/* input */)
{
    int left = 0, best = int.MaxValue;

    for (int right = 0; right < n; right++)
    {
        Add(right);

        while (IsValid())                 // shortest → shrink while VALID, recording as you go
        {
            best = Math.Min(best, right - left + 1);
            Remove(left);
            left++;
        }
    }
    return best == int.MaxValue ? 0 : best;
}

Add/Remove/IsValid model whatever the problem needs to track — a HashSet<char> for membership, a frequency array for a count threshold, a need/have pair of dictionaries for exact matching. Every problem below is one of these three skeletons with different Add/Remove/ IsValid.

problems

Four problems, one fixed-window and three variable-window — the last one combines both shrink disciplines’ cousin (need/have counting) into the hardest shape in the pattern.

1. 01Max Sum Subarray of Size Keasy

   Fixed window: add the entering element, remove the leaving one.

2. 02Longest Substring Without Repeating CharactersmediumLC #3▶ interactive

   Variable window, shrink while invalid; the HashSet is the window's memory.

3. 03Longest Repeating Character ReplacementmediumLC #424

   Window validity from a frequency count: len − maxFreq ≤ k.

4. 04Minimum Window SubstringhardLC #76

   Shortest valid window: shrink while valid, record during shrinking.