# Sliding window without the guesswork

Oct 18, 2026 · @Utkarsh Shrivastava

Sliding window turns "check every subarray" (O(n²)) into one pass (O(n)). Grow the window on the right, shrink it on the left, and keep state you can update in O(1).

## 1\. Spot it

Use a sliding window when all three are true:

*   The answer is a **contiguous** subarray or substring.
    
*   You want the **longest, shortest, a count, or every window of size k**.
    
*   Adding or removing one element updates your state in **O(1)**.
    

Watch out for subarray sums with negative numbers. Growing the window doesn't always grow the sum, so use prefix sums instead.

## 2\. Fill three blanks

Before coding, write down:

1.  **State:** what you track, like letter counts, a sum, or a set.
    
2.  **Valid:** when the window is OK, like `size - max(counts) <= k`.
    
3.  **Goal:** longest, shortest, count, or fixed size. This picks your template.
    

## 3\. Pick a template

Every loop adds `right`, shrinks from `left`, and updates the answer. The goal only changes when you shrink and where you update.

| Goal | Shrink while | Update the answer |
| --- | --- | --- |
| Longest | invalid | after shrinking |
| Shortest | valid | inside the shrink loop |
| Count | invalid | after shrinking, add `right - left + 1` |
| Fixed size k | window is bigger than k | once the window reaches size k |

**Longest**

```python
left = 0
for right in range(len(s)):
    add(s[right])
    while not valid():
        remove(s[left])
        left += 1
    best = max(best, right - left + 1)
```

Practice: [3\. Longest Substring Without Repeating Characters](https://leetcode.com/problems/longest-substring-without-repeating-characters/), [424\. Longest Repeating Character Replacement](https://leetcode.com/problems/longest-repeating-character-replacement/)

**Shortest**

```python
left = 0
for right in range(len(s)):
    add(s[right])
    while valid():
        best = min(best, right - left + 1)
        remove(s[left])
        left += 1
```

Practice: [209\. Minimum Size Subarray Sum](https://leetcode.com/problems/minimum-size-subarray-sum/), [76\. Minimum Window Substring](https://leetcode.com/problems/minimum-window-substring/)

**Count**

```python
left = 0
for right in range(len(s)):
    add(s[right])
    while not valid():
        remove(s[left])
        left += 1
    total += right - left + 1   # every valid window ending at right
```

For "exactly k", count `at_most(k) - at_most(k - 1)`.

Practice: [713\. Subarray Product Less Than K](https://leetcode.com/problems/subarray-product-less-than-k/), [992\. Subarrays with K Different Integers](https://leetcode.com/problems/subarrays-with-k-different-integers/)

**Fixed size k**

```python
for right in range(len(s)):
    add(s[right])
    if right >= k:
        remove(s[right - k])        # the element leaving
    if right >= k - 1:
        best = max(best, state())
```

Practice: [567\. Permutation in String](https://leetcode.com/problems/permutation-in-string/), [239\. Sliding Window Maximum](https://leetcode.com/problems/sliding-window-maximum/) (needs a monotonic deque)

## 4\. Test it

Trace three inputs by hand, writing `left`, `right`, and the answer at each step:

1.  **The given example.** Your trace should match the expected output.
    
2.  **Everything valid**, like `AAAA`. The answer should be the whole input.
    
3.  **Tiny input**, like one element or an empty string. No crash, and the answer is 0 or 1.
    

Then check one rule: each element is added once and removed at most once. If something is added twice, `right` is moving wrong.