Sliding window (variable)

How does Sliding window (variable) work?

The window starts empty, with both ends at index zero. A counter or a map describes what it holds.

The right end steps forward and takes in one element. Update the description with that element.

Check the condition against the current window. While it holds, record the width or the count.

When it breaks, the left end steps forward. Remove that element from the description.

Keep shrinking until the condition holds again. Only then does the right end move on.

Neither end ever steps back. So every element enters once and leaves once.

1. window = aLongest stretch with no repeated letter. The best is 1.
2. window = abb enters and is new. The best becomes 2.
3. window = abcc enters and is new. The best becomes 3.
4. window = abcbA second b enters. The window now holds b twice.
5. window = cbThe left end drops a and the first b. The best stays 3.

function longestUnder(arr, limit) {
    let left = 0;
    let sum = 0;
    let best = 0;
    for (let right = 0; right < arr.length; right++) {
        sum += arr[right];
        while (sum > limit) {
            sum -= arr[left];
            left++;
        }
        best = Math.max(best, right - left + 1);
    }
    return best;
}

A worked example of Sliding window (variable)

Longest stretch with k distinct characters

You get a string and a number k. Find the longest stretch that uses at most k different characters.

The stretch has to be contiguous, not scattered.

Grow the window to the right and count each character in a map.

Once the map holds more than k keys, shrink from the left. Measure the width after every shrink.

function longestKDistinct(s, k) {
    const count = new Map();
    let left = 0;
    let best = 0;

    for (let right = 0; right < s.length; right++) {
        count.set(s[right], (count.get(s[right]) ?? 0) + 1);

        while (count.size > k) {
            const out = s[left];
            count.set(out, count.get(out) - 1);
            if (count.get(out) === 0) count.delete(out); // the key must go, not just the count
            left++;
        }

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

    return best;
}

When should you use Sliding window (variable)?

These phrases in a problem statement point here:

• •longest/shortest contiguous subarray or substring
• •satisfying a condition (sum <= K, at most, without breaking a limit)
• •at most K distinct, no repeated element, contains all of X
• •contiguous span, not a subsequence

What is Sliding window (variable) confused with?

• Sliding window (fixed size): A fixed window is k wide from the first step to the last. This one picks its own width.
• Two pointers (opposite ends): Those start apart on sorted data and converge to one pair. Here both ends move the same way.
• Prefix sums: Prefix sums handle negative values and arbitrary ranges. Shrinking assumes removing a value helps.
• Hash set / map: A map on its own describes the whole collection. The window needs counts for the live span.

Common mistakes with Sliding window (variable)

• Leaving a zero count in the map

  The size still counts a key whose count fell to zero. Delete the key when it empties.

• Shrinking with an if instead of a while

  One removal may not be enough to restore the condition. Shrink until it holds again.

• Using it where values can be negative

  Dropping a value from the left may raise the sum. Then shrinking proves nothing.

• Measuring the width wrong

  The width is right minus left plus one. Dropping the plus one loses a character.

Which interview problems use Sliding window (variable)?

• Longest substring without repeating characters: Shrink until the duplicate letter is gone.
• Minimum size subarray sum: Grow until the sum is enough, then shrink while it stays enough.
• Longest substring with at most k distinct characters: The map size is the condition.
• Longest repeating character replacement: Width minus the most common count must stay under k.
• Minimum window substring: Grow until every needed letter is covered, then tighten.
• Fruit into baskets: At most two distinct types, the same shape as k distinct.
• Max consecutive ones III: Shrink once the window holds more than k zeroes.

What is the time and space complexity of Sliding window (variable)?

O(n)

n up to 1e6 and one best span gives O(n). Each end advances at most n times.