---
title: "Sliding window (variable)"
url: https://algopath.pro/patterns/sliding-window-variable
language: en
summary: "Grow the window from the right, and shrink it from the left when the condition breaks. Neither end ever moves backwards."
updated: 2026-08-24
---

# Sliding window (variable)

Grow the window from the right, and shrink it from the left when the condition breaks. Neither end ever moves backwards.

## 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.

- `window = a` Longest stretch with no repeated letter. The best is 1.
- `window = ab` b enters and is new. The best becomes 2.
- `window = abc` c enters and is new. The best becomes 3.
- `window = abcb` A second b enters. The window now holds b twice.
- `window = cb` The left end drops a and the first b. The best stays 3.

## When should you use Sliding window (variable)?

- 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.

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

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

## 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.

```javascript
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;
}
```

## 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.

## JavaScript

```javascript
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;
}
```

## Python

```python
def longest_under(arr, limit):
    left = 0
    total = 0
    best = 0
    for right, x in enumerate(arr):
        total += x
        while total > limit:
            total -= arr[left]
            left += 1
        best = max(best, right - left + 1)
    return best
```

## PHP

```php
function longestUnder(array $arr, int $limit): int {
    $left = 0;
    $sum = 0;
    $best = 0;
    for ($right = 0; $right < count($arr); $right++) {
        $sum += $arr[$right];
        while ($sum > $limit) {
            $sum -= $arr[$left];
            $left++;
        }
        $best = max($best, $right - $left + 1);
    }
    return $best;
}
```