Variable-Size Sliding Window: Longest and Shortest

EditorialUpdated Oct 25, 2026

When the window's size isn't given

A music app wants the longest run of songs in your history with no artist repeated. That's a window again, a run of consecutive items, but this time nobody tells you how long it is. The answer might be 3 songs or 300. With letters for artists, it's Longest Substring Without Repeating Characters, one of the most asked interview problems there is.

Checking every run is hopeless: 100,000 songs have 5,000,050,000 runs. Introduction to Sliding Window slid a window of one fixed size. Here the window has to change size as it goes: it grows on the right to take in more, and shrinks on the left when what's inside breaks the rule.

The problems in this lesson ask for the longest window that follows a rule (no repeated letter, at most k zeros, at most k different letters) or the shortest one that reaches a goal (a sum of at least a target). One loop handles all of them.

Variable-size sliding window on the string abcabcbb with the rule no repeated letter. First the window grows to abc, which follows the rule. Growing once more takes in a second a, so abca breaks the rule. The window then shrinks from the left: the first a leaves and the window bca follows the rule again. The right pointer only grows the window and the left pointer only shrinks it, and neither ever moves back.

Grow on the right, shrink on the left

Here's the loop for Longest Substring Without Repeating Characters:

Move right one step: the letter there joins the window.
While the window breaks the rule (some letter appears twice), move left one step: the letter there leaves.
Now the window follows the rule. If it's the longest so far, remember its length.

On "abcabcbb":

Longest window with no repeated letter — The window is shaded. A glowing letter has just entered; an amber one has just left; the orange letters are the repeat that breaks the rule.

The answer is 3. Notice how little work that was: right moved 8 times and left moved 7 times. Neither ever moves back, so each moves at most n times, and the whole scan is O(n), even though there's a loop inside a loop. Count how often each pointer moves, not how deeply the loops nest.

Why shrinking never skips the answer

Moving left throws windows away for good: once left passes 0, no window starting at 0 will ever be looked at again. So why is that safe?

Because of one property of the rule. A window inside a window that follows the rule also follows it. If "bcad" has no repeated letter, neither does "bca" or "cad". Turn that around: if [left, right] breaks the rule, every longer window that contains it breaks the rule too. In particular, every window that starts at left and ends at right or later is out. There's nothing left to find from that start, so left can move on.

It's the same argument as the pair grid in Introduction to Two Pointers: one look (this window breaks the rule) rules out a whole row of candidates (every longer window from this start), so the pointer that owns that row moves on. A rule with this property is called monotone, and it's the one thing to check before you reach for this pattern.

Why the left pointer can move on. On the string abcabcbb, the window from index 0 to index 3, abca, holds two a's and breaks the rule. Every longer window that starts at index 0, abcab, abcabc, abcabcb and abcabcbb, contains abca and so contains both a's: they all break the rule too. None of them can be the answer, so the left pointer leaves index 0 for good without checking them.

Try it yourself

You drive the window below. Grow moves right, Shrink moves left, and neither moves back. Follow the template (grow while the window follows the rule, shrink while it breaks it) and you'll always end with the best answer. Then break it on purpose: shrink a window that still follows the rule and watch what you lose. When a move puts the best window behind a pointer, it's marked with a dashed red line.

Switch rules to try at most k zeros, at most k different letters, and the shortest window whose sum reaches a target.

The Window Driver: grow or shrink a sliding window yourself, and see when a move throws the answer away

Template for the longest window

The same loop in four languages, with a count per letter so the rule check is O(1):

int lengthOfLongestSubstring(const string& s) {
    unordered_map<char, int> count;          // letter counts inside the window
    int left = 0, best = 0;
    for (int right = 0; right < (int)s.size(); right++) {
        count[s[right]]++;                   // grow: the letter entering
        while (count[s[right]] > 1) {        // the window breaks the rule: shrink
            count[s[left]]--;
            left++;
        }
        best = max(best, right - left + 1);  // it follows the rule again
    }
    return best;
}

def length_of_longest_substring(s):
    count = {}                               # letter counts inside the window
    left = best = 0
    for right, ch in enumerate(s):
        count[ch] = count.get(ch, 0) + 1     # grow: the letter entering
        while count[ch] > 1:                 # the window breaks the rule: shrink
            count[s[left]] -= 1
            left += 1
        best = max(best, right - left + 1)   # it follows the rule again
    return best

static int lengthOfLongestSubstring(String s) {
    Map<Character, Integer> count = new HashMap<>();   // letter counts inside the window
    int left = 0, best = 0;
    for (int right = 0; right < s.length(); right++) {
        char ch = s.charAt(right);
        count.merge(ch, 1, Integer::sum);              // grow: the letter entering
        while (count.get(ch) > 1) {                    // the window breaks the rule: shrink
            count.merge(s.charAt(left), -1, Integer::sum);
            left++;
        }
        best = Math.max(best, right - left + 1);       // it follows the rule again
    }
    return best;
}

function lengthOfLongestSubstring(s) {
    const count = new Map();                         // letter counts inside the window
    let left = 0, best = 0;
    for (let right = 0; right < s.length; right++) {
        const ch = s[right];
        count.set(ch, (count.get(ch) || 0) + 1);     // grow: the letter entering
        while (count.get(ch) > 1) {                  // the window breaks the rule: shrink
            count.set(s[left], count.get(s[left]) - 1);
            left++;
        }
        best = Math.max(best, right - left + 1);     // it follows the rule again
    }
    return best;
}

Each prints 3, 1, 3, 0 and 5 for "abcabcbb", "bbbbb", "pwwkew", "" and "tmmzuxt". The last one is a good test: the answer, "mzuxt", starts after a repeated m and ends before a repeated t.

Only the letter that just entered can be repeated, because the window followed the rule before it arrived. That's why the while checks count[ch] and nothing else.

Shortest windows: shrink while it qualifies

Minimum Size Subarray Sum asks for the shortest window of positive numbers whose sum reaches a target. The rule points the other way now: a window that reaches the target keeps reaching it when it grows, because every number is positive.

So once [left, right] reaches the target, every window from left that ends later is longer and can't be the answer. Record the length and shrink, and keep shrinking while the window still reaches the target. When it falls short, grow.

On [2, 3, 1, 2, 4, 3] with target 7:

Shortest window reaching the target — The window is shaded. Each step either grows it (the glowing number enters) or shrinks it (the amber number leaves).

int minSubArrayLen(int target, const vector<int>& nums) {
    long long windowSum = 0;
    int left = 0, best = INT_MAX;
    for (int right = 0; right < (int)nums.size(); right++) {
        windowSum += nums[right];                 // grow: the number entering
        while (windowSum >= target) {             // it qualifies: record it, then shrink
            best = min(best, right - left + 1);
            windowSum -= nums[left];
            left++;
        }
    }
    return best == INT_MAX ? 0 : best;            // no window reached the target
}

def min_sub_array_len(target, nums):
    window_sum = left = 0
    best = None
    for right, x in enumerate(nums):
        window_sum += x                           # grow: the number entering
        while window_sum >= target:               # it qualifies: record it, then shrink
            if best is None or right - left + 1 < best:
                best = right - left + 1
            window_sum -= nums[left]
            left += 1
    return 0 if best is None else best            # no window reached the target

static int minSubArrayLen(int target, int[] nums) {
    long windowSum = 0;
    int left = 0, best = Integer.MAX_VALUE;
    for (int right = 0; right < nums.length; right++) {
        windowSum += nums[right];                 // grow: the number entering
        while (windowSum >= target) {             // it qualifies: record it, then shrink
            best = Math.min(best, right - left + 1);
            windowSum -= nums[left];
            left++;
        }
    }
    return best == Integer.MAX_VALUE ? 0 : best;  // no window reached the target
}

function minSubArrayLen(target, nums) {
    let windowSum = 0, left = 0, best = Infinity;
    for (let right = 0; right < nums.length; right++) {
        windowSum += nums[right];                 // grow: the number entering
        while (windowSum >= target) {             // it qualifies: record it, then shrink
            best = Math.min(best, right - left + 1);
            windowSum -= nums[left];
            left++;
        }
    }
    return best === Infinity ? 0 : best;          // no window reached the target
}

Each prints 2, 1, 0 and 3 for target 7 on [2, 3, 1, 2, 4, 3], target 4 on [1, 4, 4], target 11 on [1, 1, 1, 1, 1, 1, 1, 1] and target 11 on [1, 2, 3, 4, 5]. The third shows the case people forget: no window reaches the target, and the answer is 0.

What the window keeps track of

The loop never changes. What changes is what the window remembers, so the rule can be checked in O(1) as items enter and leave:

Problem	Rule	What the window keeps
Longest Subarray with Sum K (Positives)	sum exactly k, all positive	the sum; shrink while it's above k
Longest Substring Without Repeating Characters	no letter twice	a count per letter
Max Consecutive Ones III	at most k zeros	how many zeros are inside
Fruit Into Baskets	at most 2 kinds	a count per kind, and how many kinds
Longest Substring with At Most K Distinct Characters	at most k letters	a count per letter, and how many are above 0
Longest Repeating Character Replacement	length − most common count ≤ k	a count per letter
Frequency of the Most Frequent Element	after sorting, raising all to the largest costs ≤ k	the sum: the cost is largest × length − sum
Minimum Size Subarray Sum (shortest)	sum ≥ target	the sum
Minimum Window Substring (shortest)	holds every letter of t, repeats included	a count per letter, and how many are covered

Minimum Window Subsequence is the odd one out: t must appear in order, which no count can check. Its window scans forward to where t ends, then backward to the latest start.

The window that never shrinks

For a longest window there's a shortcut. Swap the while for an if: when the window breaks the rule, move left just one step. The window then never gets shorter. When it breaks the rule it slides one step at its current length, and it only grows into a window that follows the rule. So its length at the end is the answer.

Longest Repeating Character Replacement is where this matters. You may change up to k letters, so a window works when its length minus the count of its most common letter is at most k. Finding the most common count after every shrink means scanning 26 counts:

def character_replacement(s, k):
    count = [0] * 26
    left = best = 0
    for right, ch in enumerate(s):
        count[ord(ch) - 65] += 1
        while (right - left + 1) - max(count) > k:   # more than k letters to change: shrink
            count[ord(s[left]) - 65] -= 1
            left += 1
        best = max(best, right - left + 1)
    return best

The well-known fast version keeps max_freq, the highest count it has ever seen, and never lowers it, even after that letter leaves:

def character_replacement_no_shrink(s, k):
    count = [0] * 26
    left = max_freq = 0
    for right, ch in enumerate(s):
        count[ord(ch) - 65] += 1
        max_freq = max(max_freq, count[ord(ch) - 65])   # never lowered
        if (right - left + 1) - max_freq > k:          # slide one step instead of shrinking
            count[ord(s[left]) - 65] -= 1
            left += 1
    return len(s) - left                               # the window's length is the answer

Both print 4 for ("ABAB", 2) and 4 for ("AABABBA", 1), and they agree with a brute force on 400 random inputs. But a stale max_freq looks wrong, so here's why it isn't. The window grows only when (its length + 1) − max_freq ≤ k. Right after a slide there's no room to spare (length − max_freq is exactly k), so the next grow needs a bigger max_freq, and that new count was just made by the letter entering this window: it's real. And if there's been no slide since max_freq was counted, nothing has left the window, so that count is still real too. Either way the window only ever grows into one that truly works.

This only works for longest windows. For a shortest window, or for counting windows (next lesson), you need the while.

When to use a variable-size window

Clues in the problem statement:

"longest / shortest subarray or substring such that…", and the stretch must be contiguous.
"at most k": at most k zeros, k different letters, k changes. Each is a monotone rule.
"sum at least / at most" with positive numbers.

Near-misses:

"exactly k": not monotone (removing an item can fix or break it). Count it as at most k minus at most k − 1, in the next lesson.
negative numbers in a sum: below.
a fixed size: that's Introduction to Sliding Window.
"subsequence": the items needn't be next to each other, so there's no window.

When it doesn't work

Everything rests on the rule being monotone. Negative numbers break it. Take "the longest subarray with sum at most 1" on [3, -5, 3]. The same loop shrinks while the sum is too big:

def longest_sum_at_most(nums, k):
    window_sum = left = best = 0
    for right, x in enumerate(nums):
        window_sum += x
        while window_sum > k and left <= right:
            window_sum -= nums[left]
            left += 1
        best = max(best, right - left + 1)
    return best

It returns 2. But the whole array sums to 1, so the answer is 3. At the first step the window [3] sums to 3, more than 1, so the loop dropped the 3 for good. It didn't know that adding -5 next would bring the sum back down. With negative numbers, "this window breaks the rule" no longer says anything about longer windows.

With all-positive numbers the same code is right (it matches a brute force on 400 random inputs). With negatives, use prefix sums, in the Prefix Sum section.

Some rules aren't monotone even without numbers. Longest Substring with At Least K Repeating Characters wants every letter to appear at least k times: a longer window can fix a letter that was short, so a window that fails now can pass later. The known fix runs one window per number of different letters allowed, 1 to 26, and each of those is monotone again.

Common mistakes

Shrinking with if in a shortest window. if window_sum >= target:

On [1, 1, 1, 1, 7] with target 7 it returns 5, not 1. One shrink per step isn't enough: after the 7 arrives, the window can lose all four 1s and still reach 7. Shrink with while.

Recording the best before the window is fixed. best = max(...) above the while

On "abcabcbb" it returns 4: it counted "abca", which holds a twice. Record only after the window follows the rule again.

Moving left backwards. left = last[ch] + 1

The faster version jumps left straight past the last copy of the repeated letter. On "abba" it returns 3, not 2: at the second a, the last a is at 0, so left jumps back from 2 to 1. Write left = max(left, last[ch] + 1).

Returning infinity when nothing qualifies. best = float("inf")

On [1, 1, 1] with target 5 it returns inf. No window reaches 5, and the problem wants 0.

Starting over at the repeat. seen = set()

Throwing the whole window away at a repeat loses the letters after the first copy. On "dvdf" it returns 2, but "vdf" has length 3. Shrink from the left until the repeat is gone, no further.

Check yourself

Quiz

1 / 5

Multiple choice

Longest Substring Without Repeating Characters: the window is "abc" and the next letter is a. What does the template do?

Practice problems

From easier to harder:

Longest Subarray with Sum K (Positives): shrink while the sum is above k.
Longest Substring Without Repeating Characters: the template.
Max Consecutive Ones III: count the zeros inside.
Fruit Into Baskets: at most two kinds.
Longest Substring with At Most K Distinct Characters: the same with k.
Longest Repeating Character Replacement: the window that never shrinks.
Frequency of the Most Frequent Element: sort first, then a cost rule.
Minimum Size Subarray Sum: the shortest window.
Minimum Window Substring: shortest, with letter counts.
Minimum Window Subsequence: shortest, with the letters in order.

Next: Counting Subarrays with a Sliding Window, where every window the loop passes through gets counted, not just the best one.