LeetCode Patterns ·

🎯 Sliding Window

1️⃣ Core Framework

When discussing Sliding Window, I frame it as:

What problem pattern it solves
Fixed-size window vs variable-size window
Window state
Window validity condition
Expand and shrink logic
Common interview problems
Edge cases
Complexity analysis
Senior-level explanation

2️⃣ What Problem Are We Solving?

Sliding window is used for problems involving contiguous subarrays or substrings.

It helps answer questions like:

Longest substring
Shortest subarray
Maximum sum of fixed-size subarray
Minimum window containing required characters
Number of valid subarrays
Longest window satisfying a constraint

The key idea is:

Instead of recomputing every subarray from scratch,
maintain a moving window and update its state incrementally.

👉 Interview Answer

Sliding window is a two-pointer technique used for contiguous subarray or substring problems.

The right pointer expands the window, and the left pointer shrinks the window when the window becomes invalid.

By maintaining window state incrementally, we avoid checking all subarrays with nested loops and often reduce the time complexity from O(n²) to O(n).

3️⃣ Why Sliding Window Works

Brute Force Problem

A brute-force solution often checks all subarrays:

for left in range(n):
    for right in range(left, n):
        check nums[left:right]

This is usually:

O(n²)

or worse if checking the subarray also takes time.

Sliding Window Optimization

Sliding window avoids recomputing from scratch.

left → window → right

We maintain:

current sum
current count
current frequency map
current distinct count
current max/min condition

When right moves, we add a new element.

When left moves, we remove an old element.

Core Rule

Expand right to include more elements.
Shrink left when the window violates the condition.
Update the answer when the window is valid.

👉 Interview Answer

Sliding window works because the window changes gradually.

When the right pointer moves, we add one element.

When the left pointer moves, we remove one element.

Since each element enters and leaves the window at most once, the total time is usually O(n).

4️⃣ Sliding Window Types

Type 1: Fixed-Size Window

The window size is fixed.

Examples:

Maximum sum of subarray of size k
Average of subarrays of size k
Find all anagrams in a string

Pattern:

Expand right.
When window size reaches k, update answer.
Then remove left and slide forward.

Type 2: Variable-Size Window

The window size changes based on a condition.

Examples:

Longest substring without repeating characters
Minimum size subarray sum
Minimum window substring
Longest substring with at most K distinct characters

Pattern:

Expand right.
While window is invalid, shrink left.
Update answer when valid.

👉 Interview Answer

I divide sliding window problems into fixed-size and variable-size windows.

Fixed-size windows maintain exactly k elements.

Variable-size windows grow and shrink based on a validity condition.

The key is knowing when to expand, when to shrink, and when to update the result.

5️⃣ Fixed-Size Sliding Window

Problem

Find the maximum sum of a subarray of size k.

nums = [1, 2, 3, 4, 5], k = 3
answer = 12
because [3, 4, 5] has the largest sum

Code

def max_sum_subarray(nums, k):
    window_sum = 0
    best = float("-inf")

    for right in range(len(nums)):
        window_sum += nums[right]

        if right >= k - 1:
            best = max(best, window_sum)
            window_sum -= nums[right - k + 1]

    return best

Explanation

When the window reaches size k:

Update answer.
Remove the leftmost element.
Continue sliding.

👉 Interview Answer

For fixed-size sliding window problems, I maintain a window of size k.

Each time I add the right element.

Once the window reaches size k, I update the answer and remove the leftmost element.

This gives O(n) time because every element is added once and removed once.

6️⃣ Fixed-Size Window Template

def fixed_window(nums, k):
    window_state = 0
    answer = None

    for right in range(len(nums)):
        # add nums[right] to window
        window_state += nums[right]

        if right >= k - 1:
            # update answer using current window
            answer = update(answer, window_state)

            # remove leftmost element
            left = right - k + 1
            window_state -= nums[left]

    return answer

When to Use

Use this when the problem says:

subarray of size k
substring of length k
exactly k elements
fixed-length window

👉 Interview Answer

Fixed-size sliding window is appropriate when the problem explicitly requires a window of length k.

The window size does not depend on a dynamic condition.

We simply add the new element and remove the old element as the window slides.

7️⃣ Variable-Size Sliding Window

Core Idea

The window size changes based on validity.

left = 0

for right in range(len(nums)):
    add(nums[right])

    while window_is_invalid():
        remove(nums[left])
        left += 1

    update_answer()

Key Components

Every variable-size sliding window needs:

A left pointer
A right pointer
Window state
Validity condition
Answer update rule

👉 Interview Answer

Variable-size sliding window is used when we need the longest, shortest, or count of windows satisfying a condition.

The right pointer expands the window.

If the window becomes invalid, the left pointer shrinks it until it becomes valid again.

The answer is updated based on the valid window.

8️⃣ Longest Substring Without Repeating Characters

Problem

Find the length of the longest substring without repeating characters.

s = "abcabcbb"
answer = 3
because "abc" is the longest substring without duplicates

Code

def length_of_longest_substring(s):
    seen = set()
    left = 0
    best = 0

    for right in range(len(s)):
        while s[right] in seen:
            seen.remove(s[left])
            left += 1

        seen.add(s[right])
        best = max(best, right - left + 1)

    return best

Invariant

The window always satisfies:

No duplicate characters inside the window.

👉 Interview Answer

I maintain a window with no duplicate characters.

The right pointer expands the window.

If the new character already exists in the window, I move the left pointer and remove characters until the duplicate is gone.

Then I update the maximum window length.

9️⃣ Minimum Size Subarray Sum

Problem

Given positive integers, find the minimum length subarray whose sum is at least target.

nums = [2, 3, 1, 2, 4, 3], target = 7
answer = 2
because [4, 3] has sum 7

Code

def min_subarray_len(target, nums):
    left = 0
    window_sum = 0
    best = float("inf")

    for right in range(len(nums)):
        window_sum += nums[right]

        while window_sum >= target:
            best = min(best, right - left + 1)
            window_sum -= nums[left]
            left += 1

    return 0 if best == float("inf") else best

Important Assumption

This works because numbers are positive.

If negative numbers exist, the sum is no longer monotonic.

👉 Interview Answer

For minimum size subarray sum, I expand the window until the sum reaches the target.

Once the sum is large enough, I shrink from the left to find the smallest valid window.

This works because all numbers are positive, so expanding increases the sum and shrinking decreases the sum.

🔟 At Most K Distinct Characters

Problem

Find the longest substring with at most k distinct characters.

Code

def length_of_longest_substring_k_distinct(s, k):
    from collections import defaultdict

    count = defaultdict(int)
    left = 0
    best = 0

    for right in range(len(s)):
        count[s[right]] += 1

        while len(count) > k:
            count[s[left]] -= 1

            if count[s[left]] == 0:
                del count[s[left]]

            left += 1

        best = max(best, right - left + 1)

    return best

Window State

count map: character frequency inside window
len(count): number of distinct characters

👉 Interview Answer

I use a frequency map to track characters in the current window.

The window is valid when the number of distinct characters is at most k.

If distinct count exceeds k, I shrink from the left until the window becomes valid again.

Then I update the maximum length.

1️⃣1️⃣ Minimum Window Substring

Problem

Find the smallest substring of s that contains all characters from t.

s = "ADOBECODEBANC"
t = "ABC"
answer = "BANC"

Code

def min_window(s, t):
    from collections import Counter, defaultdict

    need = Counter(t)
    window = defaultdict(int)

    have = 0
    need_count = len(need)

    left = 0
    best_len = float("inf")
    best_start = 0

    for right in range(len(s)):
        char = s[right]
        window[char] += 1

        if char in need and window[char] == need[char]:
            have += 1

        while have == need_count:
            if right - left + 1 < best_len:
                best_len = right - left + 1
                best_start = left

            left_char = s[left]
            window[left_char] -= 1

            if left_char in need and window[left_char] < need[left_char]:
                have -= 1

            left += 1

    if best_len == float("inf"):
        return ""

    return s[best_start:best_start + best_len]

Key State

need: required character counts
window: current window counts
have: number of characters whose required count is satisfied
need_count: total unique required characters

👉 Interview Answer

Minimum window substring is a variable-size sliding window problem.

I expand the right pointer until the window contains all required characters.

Once valid, I shrink from the left to find the smallest valid window.

I use frequency maps to track required counts and current window counts.

1️⃣2️⃣ Find All Anagrams in a String

Problem

Find all start indexes of p’s anagrams in s.

s = "cbaebabacd"
p = "abc"
answer = [0, 6]

Fixed-Size Window

Because every anagram of p has length:

len(p)

Code

def find_anagrams(s, p):
    from collections import Counter, defaultdict

    need = Counter(p)
    window = defaultdict(int)
    result = []

    k = len(p)

    for right in range(len(s)):
        window[s[right]] += 1

        if right >= k:
            left_char = s[right - k]
            window[left_char] -= 1

            if window[left_char] == 0:
                del window[left_char]

        if window == need:
            result.append(right - k + 1)

    return result

👉 Interview Answer

Finding anagrams is a fixed-size sliding window problem.

Every anagram has the same length as p.

I maintain a frequency map for the current window and compare it with the target frequency map.

When they match, the current window is an anagram.

1️⃣3️⃣ Counting Valid Subarrays

Common Pattern

Sometimes the problem asks:

How many subarrays satisfy a condition?

For example:

number of subarrays with at most k distinct integers

Key Trick

If a window [left, right] is valid, then every subarray ending at right and starting between left and right is also valid.

So we add:

right - left + 1

Code Pattern

def count_at_most_k(nums, k):
    from collections import defaultdict

    count = defaultdict(int)
    left = 0
    result = 0

    for right in range(len(nums)):
        count[nums[right]] += 1

        while len(count) > k:
            count[nums[left]] -= 1

            if count[nums[left]] == 0:
                del count[nums[left]]

            left += 1

        result += right - left + 1

    return result

👉 Interview Answer

For counting valid subarrays, once the window is valid, all subarrays ending at right and starting from any index between left and right are also valid.

Therefore, we can add right - left + 1 to the answer.

This is a common trick for at-most-k style sliding window problems.

1️⃣4️⃣ Exactly K Problems

Important Technique

Problems asking for exactly k are often solved using at most k.

exactly(k) = at_most(k) - at_most(k - 1)

Example

Number of subarrays with exactly k distinct integers:

def subarrays_with_k_distinct(nums, k):
    return at_most_k(nums, k) - at_most_k(nums, k - 1)

Why It Works

Subarrays with at most k
minus
Subarrays with at most k - 1
equals
Subarrays with exactly k

👉 Interview Answer

For exactly-k sliding window problems, I often transform the problem into two at-most-k problems.

The formula is exactly(k) equals at_most(k) minus at_most(k - 1).

This is useful because at-most-k windows are usually easier to maintain.

1️⃣5️⃣ Window State Design

Common Window States

Problem Type	Window State
Sum problem	current sum
Product problem	current product
Duplicate problem	set or frequency map
Distinct count problem	frequency map
Min/max problem	monotonic deque
Required character problem	need/window count maps

Senior-Level Question

Ask:

What do I need to know about the current window
to decide whether it is valid?

👉 Interview Answer

The most important design decision is the window state.

For sum problems, state may be a running sum.

For duplicate or distinct problems, state is usually a set or frequency map.

For minimum or maximum inside a window, I may need a monotonic deque.

The state should allow me to check validity efficiently.

1️⃣6️⃣ When Sliding Window Does Not Work

Negative Numbers Can Break Monotonicity

For example:

Minimum subarray sum >= target

Sliding window works when all numbers are positive.

But if numbers can be negative:

[2, -1, 2]

Expanding does not always increase sum.

Shrinking does not always decrease sum.

Non-Contiguous Problems

Sliding window is for contiguous ranges.

If the problem asks for subsequence or arbitrary subset, sliding window may not apply.

No Efficient Validity Update

If the window condition cannot be updated incrementally, sliding window may not help.

👉 Interview Answer

Sliding window is not always valid.

It usually requires a contiguous range and some form of monotonic or incrementally maintainable condition.

If negative numbers break monotonicity, or if the problem is about subsequences rather than substrings or subarrays, sliding window may not be the right approach.

1️⃣7️⃣ Sliding Window vs Two Pointers

Relationship

Sliding window is a specialized two-pointer pattern.

Two pointers: general technique
Sliding window: two pointers maintaining a contiguous range

Two Pointers

Can be:

Opposite direction
Same direction
Fast and slow
Window-based

Sliding Window

Always represents:

a contiguous window [left, right]

👉 Interview Answer

Sliding window is a specific type of two pointers.

Two pointers is the broader category.

Sliding window specifically maintains a contiguous range between left and right.

It is mostly used for substring and subarray problems.

1️⃣8️⃣ Common Edge Cases

Empty Input

s = ""
nums = []

k Equals 0

k = 0

Usually requires special handling.

k Greater Than Length

k > len(nums)

For fixed-size windows, no valid window may exist.

Duplicate Characters

Important for substring problems.

Need to Update Before or After Shrinking

Some problems require:

update answer before shrinking

Others require:

update answer after shrinking

This depends on whether we want minimum or maximum window.

👉 Interview Answer

The main edge cases are empty input, k equals zero, k larger than the input length, duplicates, and update timing.

I always clarify whether the answer should be updated when the window first becomes valid or after it is shrunk to its smallest valid form.

1️⃣9️⃣ Complexity Analysis

Time Complexity

Most sliding window algorithms are:

O(n)

Because:

right moves from 0 to n - 1
left also moves from 0 to n - 1

Each element is added once and removed once.

Space Complexity

Depends on window state:

O(1) for running sum
O(k) or O(charset size) for frequency map
O(n) worst case for hash map

👉 Interview Answer

Sliding window is usually O(n) because each pointer moves monotonically.

Each element enters the window once and leaves the window once.

Space complexity depends on the state we maintain, such as a running sum, set, frequency map, or deque.

2️⃣0️⃣ Common Mistakes

Mistake 1: Using Sliding Window When Condition Is Not Monotonic

Example:

negative numbers in minimum subarray sum

Mistake 2: Updating Answer at the Wrong Time

For longest valid window:

update after making window valid

For minimum valid window:

update while window is valid before shrinking

Mistake 3: Forgetting to Remove from Frequency Map

if count[x] == 0:
    del count[x]

Mistake 4: Infinite Loop

Forgetting to move left inside the while loop.

Mistake 5: Confusing Fixed and Variable Window

Fixed-size:

window size is exactly k

Variable-size:

window size depends on condition

👉 Interview Answer

The most common mistakes are applying sliding window when the condition is not monotonic, updating the answer at the wrong time, forgetting to remove zero-count keys from the map, and confusing fixed-size with variable-size windows.

I avoid these mistakes by first defining the window invariant.

2️⃣1️⃣ Standard Templates

Fixed-Size Window Template

def fixed_window(nums, k):
    window_state = 0
    answer = None

    for right in range(len(nums)):
        add nums[right] to window_state

        if right >= k - 1:
            update answer

            left = right - k + 1
            remove nums[left] from window_state

    return answer

Variable-Size Longest Window Template

def longest_valid_window(nums):
    left = 0
    answer = 0

    for right in range(len(nums)):
        add(nums[right])

        while window_invalid():
            remove(nums[left])
            left += 1

        answer = max(answer, right - left + 1)

    return answer

Variable-Size Minimum Window Template

def minimum_valid_window(nums):
    left = 0
    answer = float("inf")

    for right in range(len(nums)):
        add(nums[right])

        while window_valid():
            answer = min(answer, right - left + 1)
            remove(nums[left])
            left += 1

    return answer

Count Valid Subarrays Template

def count_valid_windows(nums):
    left = 0
    answer = 0

    for right in range(len(nums)):
        add(nums[right])

        while window_invalid():
            remove(nums[left])
            left += 1

        answer += right - left + 1

    return answer

🧠 Staff-Level Answer Final

👉 Interview Answer Full Version

Sliding window is a two-pointer technique used for contiguous subarray or substring problems.

The core idea is to maintain a window between left and right pointers and update the window state incrementally as the window moves.

Instead of recomputing every possible subarray or substring from scratch, we add one element when the right pointer expands and remove one element when the left pointer shrinks.

This often reduces brute-force O(n²) solutions to O(n).

I usually separate sliding window problems into fixed-size and variable-size windows.

Fixed-size windows are used when the problem asks for exactly k elements or a substring of length k. In that case, we add the new right element, update the answer when the window reaches size k, and then remove the leftmost element.

Variable-size windows are used when the window size depends on a condition. The right pointer expands the window. If the window becomes invalid, the left pointer shrinks the window until it becomes valid again.

The most important part of sliding window is defining the window state and the invariant.

For sum problems, the state may be a running sum. For duplicate or distinct-character problems, the state is usually a set or frequency map. For minimum or maximum values inside a window, we may need a monotonic deque.

I also check whether sliding window is actually valid for the problem. It usually requires a contiguous range and an incrementally maintainable condition. Some problems with negative numbers break the monotonic behavior required by sliding window.

Complexity is usually O(n), because each element enters the window once and leaves the window once. Space complexity depends on the window state, such as O(1) for a running sum or O(k) / O(n) for a frequency map.

At a senior level, I would not just say “use sliding window.” I would explain what the window represents, what makes the window valid or invalid, how the state is updated, why each pointer moves monotonically, and why no candidate answer is skipped.

⭐ Final Insight

Sliding Window 的核心不是简单地移动 left 和 right。

它的核心是维护一个 window invariant。

Senior-level 的解释重点是：

当前 window 代表什么， window state 如何维护， window 什么时候 valid，什么时候 shrink，以及为什么每个元素最多进出窗口一次。

能讲清楚这些，Sliding Window 就从刷题模板变成了真正的 algorithmic reasoning pattern。

中文部分

🎯 Sliding Window

1️⃣ 核心框架

讨论 Sliding Window 时，我通常从：

它解决什么问题
固定窗口 vs 可变窗口
Window state
Window validity condition
Expand 和 shrink 逻辑
高频面试题
Edge cases
Complexity analysis
高级工程师解释方式

2️⃣ 要解决什么问题？

Sliding window 主要用于 连续 subarray 或 substring 问题。

它常用来解决：

Longest substring
Shortest subarray
Maximum sum of fixed-size subarray
Minimum window containing required characters
Number of valid subarrays
Longest window satisfying a constraint

核心思想是：

不要每次重新计算一个 subarray 或 substring，
而是维护一个移动窗口，
并且增量更新窗口状态。

👉 面试回答

Sliding window 是一种 two-pointer 技巧，主要用于连续 subarray 或 substring 问题。

right pointer 负责扩展窗口， left pointer 在窗口不合法时负责收缩窗口。

通过增量维护 window state，我们可以避免 O(n²) 的暴力枚举，通常把复杂度降到 O(n)。

3️⃣ 为什么 Sliding Window 有效？

暴力解法

很多问题的暴力解是检查所有 subarray：

for left in range(n):
    for right in range(left, n):
        check nums[left:right]

复杂度通常是：

O(n²)

如果每次还要重新计算窗口状态，可能更慢。

Sliding Window 优化

Sliding window 不重新计算整个区间。

left → window → right

我们维护：

current sum
current count
current frequency map
current distinct count
current max/min condition

right 移动时，加入新元素。

left 移动时，移除旧元素。

核心规则

Expand right to include more elements.
Shrink left when the window violates the condition.
Update the answer when the window is valid.

👉 面试回答

Sliding window 有效，是因为窗口每次只变化一个元素。

right pointer 移动时，加入一个元素。

left pointer 移动时，移除一个元素。

每个元素最多进入窗口一次、离开窗口一次，所以总复杂度通常是 O(n)。

4️⃣ Sliding Window 类型

Type 1: 固定大小窗口

窗口大小固定。

例如：

Maximum sum of subarray of size k
Average of subarrays of size k
Find all anagrams in a string

模式：

right 扩展窗口。
当窗口大小达到 k，更新答案。
然后移除 left，窗口向前滑动。

Type 2: 可变大小窗口

窗口大小根据条件变化。

例如：

Longest substring without repeating characters
Minimum size subarray sum
Minimum window substring
Longest substring with at most K distinct characters

模式：

right 扩展窗口。
当 window invalid 时，移动 left 收缩窗口。
当 window valid 时，更新答案。

👉 面试回答

我会把 sliding window 分成 fixed-size 和 variable-size 两类。

Fixed-size window 用于窗口长度明确是 k 的问题。

Variable-size window 用于窗口大小由条件决定的问题。

关键是判断什么时候 expand，什么时候 shrink，以及什么时候 update answer。

5️⃣ 固定大小 Sliding Window

Problem

找 size 为 k 的 subarray 的最大 sum。

nums = [1, 2, 3, 4, 5], k = 3
answer = 12
because [3, 4, 5] has the largest sum

Code

def max_sum_subarray(nums, k):
    window_sum = 0
    best = float("-inf")

    for right in range(len(nums)):
        window_sum += nums[right]

        if right >= k - 1:
            best = max(best, window_sum)
            window_sum -= nums[right - k + 1]

    return best

Explanation

当窗口达到 size k：

更新答案
移除最左边元素
继续滑动

👉 面试回答

对固定大小窗口问题，我维护一个 size 为 k 的 window。

每次加入 right 指向的新元素。

当窗口达到 k 个元素时，更新答案，然后移除最左边元素。

因为每个元素只加入一次、移除一次，所以复杂度是 O(n)。

6️⃣ 固定窗口模板

def fixed_window(nums, k):
    window_state = 0
    answer = None

    for right in range(len(nums)):
        # add nums[right] to window
        window_state += nums[right]

        if right >= k - 1:
            # update answer using current window
            answer = update(answer, window_state)

            # remove leftmost element
            left = right - k + 1
            window_state -= nums[left]

    return answer

什么时候用？

当题目说：

subarray of size k
substring of length k
exactly k elements
fixed-length window

👉 面试回答

Fixed-size sliding window 适合窗口长度明确固定的问题。

window size 不依赖动态条件。

我们只需要每次加入新元素，当窗口达到 k 时更新答案，然后移除最左边元素。

7️⃣ 可变大小 Sliding Window

核心思想

窗口大小根据条件变化。

left = 0

for right in range(len(nums)):
    add(nums[right])

    while window_is_invalid():
        remove(nums[left])
        left += 1

    update_answer()

关键组成

每个 variable-size sliding window 都需要：

left pointer
right pointer
window state
validity condition
answer update rule

👉 面试回答

Variable-size sliding window 用于寻找满足条件的最长、最短，或者统计满足条件的窗口数量。

right pointer 负责扩展窗口。

如果窗口变得 invalid， left pointer 负责收缩窗口，直到窗口重新 valid。

答案根据 valid window 更新。

8️⃣ Longest Substring Without Repeating Characters

Problem

找最长的不含重复字符的 substring。

s = "abcabcbb"
answer = 3
because "abc" is the longest substring without duplicates

Code

def length_of_longest_substring(s):
    seen = set()
    left = 0
    best = 0

    for right in range(len(s)):
        while s[right] in seen:
            seen.remove(s[left])
            left += 1

        seen.add(s[right])
        best = max(best, right - left + 1)

    return best

Invariant

窗口始终满足：

window 中没有重复字符

👉 面试回答

我维护一个没有重复字符的窗口。

right pointer 扩展窗口。

如果新加入的字符已经存在，就移动 left pointer 并移除字符，直到 duplicate 被移除。

然后更新最大窗口长度。

9️⃣ Minimum Size Subarray Sum

Problem

给定正整数数组，找到 sum 至少为 target 的最短 subarray 长度。

nums = [2, 3, 1, 2, 4, 3], target = 7
answer = 2
because [4, 3] has sum 7

Code

def min_subarray_len(target, nums):
    left = 0
    window_sum = 0
    best = float("inf")

    for right in range(len(nums)):
        window_sum += nums[right]

        while window_sum >= target:
            best = min(best, right - left + 1)
            window_sum -= nums[left]
            left += 1

    return 0 if best == float("inf") else best

重要前提

这个解法成立是因为数字都是 positive。

如果有 negative numbers：

sum 不再单调

👉 面试回答

对 minimum size subarray sum，我先扩展 right pointer，直到 window sum 达到 target。

一旦 window valid，我就移动 left pointer 尝试缩小窗口，找到最短的 valid window。

这个方法成立的原因是所有数都是正数，所以扩展会增加 sum，收缩会减少 sum。

🔟 At Most K Distinct Characters

Problem

找最多包含 k 个 distinct characters 的最长 substring。

Code

def length_of_longest_substring_k_distinct(s, k):
    from collections import defaultdict

    count = defaultdict(int)
    left = 0
    best = 0

    for right in range(len(s)):
        count[s[right]] += 1

        while len(count) > k:
            count[s[left]] -= 1

            if count[s[left]] == 0:
                del count[s[left]]

            left += 1

        best = max(best, right - left + 1)

    return best

Window State

count map: character frequency inside window
len(count): distinct character count

👉 面试回答

我用 frequency map 记录当前窗口中每个字符的出现次数。

当 distinct count 小于等于 k 时，窗口 valid。

如果 distinct count 超过 k，就移动 left pointer 收缩窗口，直到窗口重新 valid。

然后更新最大长度。

1️⃣1️⃣ Minimum Window Substring

Problem

找 s 中最短的 substring，使它包含 t 中所有字符。

s = "ADOBECODEBANC"
t = "ABC"
answer = "BANC"

Code

def min_window(s, t):
    from collections import Counter, defaultdict

    need = Counter(t)
    window = defaultdict(int)

    have = 0
    need_count = len(need)

    left = 0
    best_len = float("inf")
    best_start = 0

    for right in range(len(s)):
        char = s[right]
        window[char] += 1

        if char in need and window[char] == need[char]:
            have += 1

        while have == need_count:
            if right - left + 1 < best_len:
                best_len = right - left + 1
                best_start = left

            left_char = s[left]
            window[left_char] -= 1

            if left_char in need and window[left_char] < need[left_char]:
                have -= 1

            left += 1

    if best_len == float("inf"):
        return ""

    return s[best_start:best_start + best_len]

Key State

need: required character counts
window: current window counts
have: 已经满足要求的字符种类数
need_count: 需要满足的字符种类数

👉 面试回答

Minimum window substring 是 variable-size sliding window。

我用 right pointer 扩展窗口，直到窗口包含所有 required characters。

当窗口 valid 后，我移动 left pointer 尝试缩小窗口，并记录最短 valid window。

这里需要 frequency map 来维护 required count 和 current window count。

1️⃣2️⃣ Find All Anagrams in a String

Problem

找出 s 中所有 p 的 anagram 的起始 index。

s = "cbaebabacd"
p = "abc"
answer = [0, 6]

为什么是固定窗口？

因为每个 anagram 的长度都是：

len(p)

Code

def find_anagrams(s, p):
    from collections import Counter, defaultdict

    need = Counter(p)
    window = defaultdict(int)
    result = []

    k = len(p)

    for right in range(len(s)):
        window[s[right]] += 1

        if right >= k:
            left_char = s[right - k]
            window[left_char] -= 1

            if window[left_char] == 0:
                del window[left_char]

        if window == need:
            result.append(right - k + 1)

    return result

👉 面试回答

Find all anagrams 是 fixed-size sliding window。

因为每个 anagram 的长度都等于 p 的长度。

我维护当前窗口的 frequency map，并和 p 的 frequency map 比较。

如果相等，说明当前窗口是一个 anagram。

1️⃣3️⃣ 统计 Valid Subarrays

常见题型

有些题会问：

有多少个 subarrays 满足条件？

例如：

number of subarrays with at most k distinct integers

核心技巧

如果 [left, right] 是 valid window，

那么所有以 right 结尾、起点在 left 到 right 之间的 subarray 都是 valid。

所以加：

right - left + 1

Code Pattern

def count_at_most_k(nums, k):
    from collections import defaultdict

    count = defaultdict(int)
    left = 0
    result = 0

    for right in range(len(nums)):
        count[nums[right]] += 1

        while len(count) > k:
            count[nums[left]] -= 1

            if count[nums[left]] == 0:
                del count[nums[left]]

            left += 1

        result += right - left + 1

    return result

👉 面试回答

对 count valid subarrays 的题，如果当前窗口 [left, right] 是 valid，那么所有以 right 结尾、从 left 到 right 任意位置开始的 subarray 都是 valid。

所以每次可以加 right - left + 1。

这是 at-most-k 类型题的常见技巧。

1️⃣4️⃣ Exactly K 问题

重要技巧

Exactly k 经常可以转化成 at most k。

exactly(k) = at_most(k) - at_most(k - 1)

Example

统计 exactly k distinct integers 的 subarrays：

def subarrays_with_k_distinct(nums, k):
    return at_most_k(nums, k) - at_most_k(nums, k - 1)

为什么正确？

最多 k 个
减去
最多 k - 1 个
等于
正好 k 个

👉 面试回答

对 exactly-k 类型的 sliding window 问题，我经常把它转化成两个 at-most-k 问题。

公式是 exactly(k) = at_most(k) - at_most(k - 1)。

因为 at-most-k 的窗口条件通常更容易维护。

1️⃣5️⃣ Window State 设计

常见 Window State

Problem Type	Window State
Sum problem	current sum
Product problem	current product
Duplicate problem	set or frequency map
Distinct count problem	frequency map
Min/max problem	monotonic deque
Required character problem	need/window count maps

高级工程师应该问

我需要知道当前 window 的哪些信息，
才能判断它是否 valid？

👉 面试回答

Sliding window 最重要的设计点是 window state。

对 sum problem，state 通常是 running sum。

对 duplicate 或 distinct problem，state 通常是 set 或 frequency map。

对窗口内 max/min problem，可能需要 monotonic deque。

Window state 的目标是让 validity check 足够高效。

1️⃣6️⃣ 什么时候 Sliding Window 不适用？

Negative Numbers 可能破坏单调性

例如：

Minimum subarray sum >= target

如果所有数都是 positive，sliding window 有效。

但如果有 negative numbers：

[2, -1, 2]

扩展窗口不一定增加 sum。

收缩窗口也不一定减少 sum。

非连续问题

Sliding window 只适合 contiguous range。

如果题目问的是：

subsequence
arbitrary subset

通常不适合 sliding window。

Condition 不能增量维护

如果 window condition 不能高效更新， sliding window 也不一定有帮助。

👉 面试回答

Sliding window 不是所有题都能用。

它通常要求问题是 contiguous range，并且 window condition 可以增量维护。

如果 negative numbers 破坏了 sum 的单调性，或者题目是 subsequence 而不是 substring/subarray，那 sliding window 可能不是正确方法。

1️⃣7️⃣ Sliding Window vs Two Pointers

关系

Sliding window 是 two pointers 的一种特殊形式。

Two pointers: 更通用的技巧
Sliding window: 维护一个连续区间

Two Pointers 可以是：

Opposite direction
Same direction
Fast and slow
Window-based

Sliding Window 一定表示：

一个连续 window [left, right]

👉 面试回答

Sliding window 是 two pointers 的一个子类型。

Two pointers 是更大的概念。

Sliding window 特指用 left 和 right 维护一个连续区间。

它主要用于 substring 和 subarray 问题。

1️⃣8️⃣ 常见 Edge Cases

Empty Input

s = ""
nums = []

k Equals 0

k = 0

通常需要特殊处理。

k Greater Than Length

k > len(nums)

固定窗口问题中可能不存在 valid window。

Duplicate Characters

substring 问题中特别常见。

Update Timing

有的题需要：

update answer before shrinking

有的题需要：

update answer after shrinking

取决于你要找 longest 还是 minimum。

👉 面试回答

常见 edge cases 包括 empty input、k 等于 0、k 大于数组长度、duplicates、以及 update timing。

我会特别注意：是在 window valid 时更新答案，还是在 shrink 之后更新答案。

这通常取决于题目要 longest window 还是 minimum window。

1️⃣9️⃣ Complexity Analysis

Time Complexity

多数 sliding window 是：

O(n)

原因是：

right 从 0 到 n - 1
left 也最多从 0 到 n - 1

每个元素最多加入一次、移除一次。

Space Complexity

取决于 window state：

O(1) for running sum
O(k) or O(charset size) for frequency map
O(n) worst case for hash map

👉 面试回答

Sliding window 通常是 O(n)，因为两个 pointer 都是单向移动。

每个元素最多进入窗口一次、离开窗口一次。

Space complexity 取决于维护的 state，比如 running sum、set、frequency map 或 deque。

2️⃣0️⃣ 常见错误

Mistake 1: 在不满足单调性的题上强行使用 Sliding Window

例如：

negative numbers in minimum subarray sum

Mistake 2: 答案更新时机错误

找 longest valid window：

make window valid first, then update answer

找 minimum valid window：

while window is valid, update answer before shrinking

Mistake 3: 忘记从 Frequency Map 删除 0 count

if count[x] == 0:
    del count[x]

Mistake 4: Infinite Loop

在 while loop 中忘记移动 left。

Mistake 5: 混淆 Fixed Window 和 Variable Window

Fixed-size:

window size is exactly k

Variable-size:

window size depends on condition

👉 面试回答

Sliding window 常见错误包括：在不满足单调性的题上使用它、答案更新时机错误、 frequency map 没删除 0 count、忘记移动 left 导致 infinite loop、以及混淆 fixed-size 和 variable-size window。

我通常通过先定义 window invariant 来避免这些问题。

2️⃣1️⃣ 标准模板

Fixed-Size Window Template

def fixed_window(nums, k):
    window_state = 0
    answer = None

    for right in range(len(nums)):
        add nums[right] to window_state

        if right >= k - 1:
            update answer

            left = right - k + 1
            remove nums[left] from window_state

    return answer

Variable-Size Longest Window Template

def longest_valid_window(nums):
    left = 0
    answer = 0

    for right in range(len(nums)):
        add(nums[right])

        while window_invalid():
            remove(nums[left])
            left += 1

        answer = max(answer, right - left + 1)

    return answer

Variable-Size Minimum Window Template

def minimum_valid_window(nums):
    left = 0
    answer = float("inf")

    for right in range(len(nums)):
        add(nums[right])

        while window_valid():
            answer = min(answer, right - left + 1)
            remove(nums[left])
            left += 1

    return answer

Count Valid Subarrays Template

def count_valid_windows(nums):
    left = 0
    answer = 0

    for right in range(len(nums)):
        add(nums[right])

        while window_invalid():
            remove(nums[left])
            left += 1

        answer += right - left + 1

    return answer

🧠 Staff-Level Answer Final

👉 面试回答完整版本

Sliding window 是一种用于 contiguous subarray 或 substring 问题的 two-pointer 技巧。

核心思想是用 left 和 right pointer 维护一个 window，并在窗口移动时增量更新 window state。

相比暴力枚举所有 subarray 或 substring， sliding window 不会每次从头计算窗口内容。

right pointer 移动时加入一个元素， left pointer 移动时移除一个元素。

这样通常可以把 O(n²) 的解法优化成 O(n)。

我通常把 sliding window 分成 fixed-size 和 variable-size 两类。

Fixed-size window 用于题目明确要求 size 为 k 的窗口。比如 size k 的最大 subarray sum，或者找所有长度为 len(p) 的 anagram。

Variable-size window 用于窗口大小由条件决定的题。 right pointer 负责扩展窗口。如果窗口 invalid，就移动 left pointer 收缩窗口，直到重新 valid。

Sliding window 最关键的是定义 window state 和 invariant。

对 sum problem，state 可能是 running sum。对 duplicate 或 distinct problem，state 通常是 set 或 frequency map。对窗口内最大值或最小值问题，可能需要 monotonic deque。

我也会判断 sliding window 是否真的适用。它通常要求问题是连续区间，并且 condition 可以增量维护。如果有 negative numbers 破坏单调性，或者问题问的是 subsequence 而不是 substring/subarray， sliding window 可能不是正确方法。

复杂度通常是 O(n)，因为每个元素最多进入窗口一次、离开窗口一次。

高级工程师解释 sliding window 时，不能只说“用 sliding window 模板”。

要讲清楚： window 代表什么， window state 是什么， window valid/invalid 的条件是什么， left 和 right 什么时候移动，以及为什么不会跳过任何可能的答案。

⭐ Final Insight

Sliding Window 的核心不是 left/right 两个变量。

它的核心是维护一个动态 window invariant。

Senior-level 的重点是：

当前 window 表示什么， state 如何增量维护，什么情况下 expand，什么情况下 shrink，以及为什么整体只需要 O(n)。

讲清楚这些，Sliding Window 就不是模板题，而是一个可以解释、证明、扩展的算法模式。