GL
GrindLens
PatternsSheetsPricingQuestions
  1. Home
  2. /Patterns
  3. /Sliding Window (Variable Size)
←All Patterns
Sliding WindowEvidence Contributing

Sliding Window (Variable Size)

Expand and shrink a window's right/left edges based on a validity condition to find an optimal-length substring/subarray.

Practice Problems: 5
Difficulty: 1 Easy·3 Medium·1 Hard

Core technique

Maintain a contiguous window while both edges move forward. For longest-window problems, shrink when the window becomes invalid. For shortest-window problems, shrink while it is valid and record candidates before removing elements. Each index enters once and leaves at most once, so constant-time updates give a linear scan.

How to recognize it

  • The question asks for the longest or shortest contiguous subarray or substring that satisfies a condition.
  • The condition can be tracked incrementally with a count map, a running sum, or a distinct counter.
  • The condition changes predictably as either edge moves. Removing characters can repair an at-most limit; for a minimum-sum target over non-negative numbers, removing values moves toward invalid instead.
  • The statement says at most K distinct, without repeating, minimum window, or sum at least target.

Template

This version finds the longest window with at most k distinct characters, for an integer k >= 0. These templates assume ASCII input so character counting is consistent across languages. Measure after shrinking. For shortest-window problems, record the answer while the window is still valid, then shrink.

Python

def longest_at_most_k_distinct(s, k):
    counts = {}
    left = best = 0
    for right, ch in enumerate(s):
        counts[ch] = counts.get(ch, 0) + 1
        while len(counts) > k:
            counts[s[left]] -= 1
            if counts[s[left]] == 0:
                del counts[s[left]]
            left += 1
        best = max(best, right - left + 1)
    return best

Java

int longestAtMostKDistinct(String s, int k) {
    Map<Character, Integer> counts = new HashMap<>();
    int left = 0, best = 0;
    for (int right = 0; right < s.length(); right++) {
        counts.merge(s.charAt(right), 1, Integer::sum);
        while (counts.size() > k) {
            char drop = s.charAt(left);
            if (counts.merge(drop, -1, Integer::sum) == 0) counts.remove(drop);
            left++;
        }
        best = Math.max(best, right - left + 1);
    }
    return best;
}

JavaScript

function longestAtMostKDistinct(s, k) {
  const counts = new Map();
  let left = 0;
  let best = 0;
  for (let right = 0; right < s.length; right++) {
    counts.set(s[right], (counts.get(s[right]) ?? 0) + 1);
    while (counts.size > k) {
      const drop = s[left];
      counts.set(drop, counts.get(drop) - 1);
      if (counts.get(drop) === 0) counts.delete(drop);
      left++;
    }
    best = Math.max(best, right - left + 1);
  }
  return best;
}

Worked example: Longest Substring Without Repeating Characters

  1. Run it on abcabcbb. The window is valid when no character repeats. The template swaps the distinct-count check for a duplicate check, and the shape is identical.
  2. The right edge reads a, b, c. The window grows to abc, length 3.
  3. The right edge reads a again. Shrink from the left past the first a, which leaves bca, still length 3.
  4. The right edge reads b, then c. Each time the older copy leaves first, giving cab and then abc.
  5. The right edge reads the b at index 6. Shrinking past the older b leaves cb. The final b shrinks the window to b.
  6. The best length seen is 3, which is the answer.

Complexity: For the no-repeating example: O(n) time and O(min(n, alphabet size)) extra space. For the at-most-k template: O(n) time and O(min(n, k + 1)) extra space, including the temporary character that triggers shrinking.

Try Longest Substring Without Repeating Characters on LeetCode↗

Common mistakes

  • Recording the best length before the shrink loop finishes. That counts a window that is not valid yet.
  • Forgetting to delete a key when its count reaches zero, so the distinct count never goes down.
  • Using the usual sum-window rules with negative numbers. Removing a value can increase the sum. Exact-sum counting can use prefix sums with a hash map; shortest-subarray-at-least-target problems may need prefix sums with a monotonic deque.
  • Getting the length wrong by one. A window from left to right inclusive holds right - left + 1 elements.
  • Confusing counting with longest-window problems. To count subarrays with exactly K distinct values, subtract the at-most-(K - 1) count from the at-most-K count. That subtraction does not compute the longest length.

When this pattern does not fit

  • The chosen elements do not have to be contiguous. That is usually dynamic programming or greedy.
  • The condition is not monotonic, for example a sum over values that can be negative.
  • The window size is fixed at K. The fixed-size window is simpler: add one element, drop one element, and no shrink loop is needed.

Canonical Practice Problems

5 problems
1.Best Time to Buy and Sell StockEasy
Solve on LeetCode↗
2.Longest Repeating Character ReplacementMedium
Solve on LeetCode↗
3.Longest Substring Without Repeating CharactersMedium
Solve on LeetCode↗
4.Minimum Size Subarray SumMedium
Solve on LeetCode↗
5.Minimum Window SubstringHard
Solve on LeetCode↗

Curated Sheets Containing This Pattern

NeetCode All

5 problems

→

Blind 75

4 problems

→

LeetCode Top Interview 150

4 problems

→

NeetCode 150

4 problems

→

Striver A2Z

4 problems

→

Striver SDE Sheet

2 problems

→

Love Babbar 450

1 problem

→

Related Algorithmic Patterns

Hashing1 shared

Hashmap Frequency / State Counting

Arrays1 shared

Prefix Sum

Sliding Window

Sliding Window (Fixed Size)

GL
GrindLens

Precision pattern analytics and curated sheet tracking for algorithmic coding interview preparation.

Quick lookup:⌘Kor/

Platform

  • Patterns→
  • Sheets→
  • Pricing→

Community

  • Feedback
  • Report a bug
  • X
  • LinkedIn

© 2026 GrindLens. LeetCode is a trademark of LeetCode. GrindLens is an independent analytics platform and is not affiliated with or endorsed by LeetCode.

Terms of ServicePrivacy Policy