reference: Lingchashan Aifu

Fixed-size Sliding Window

Entry: The element at index i enters the window, update relevant statistics. If i<k-1, repeat the first step.

Update: Update the answer. Generally, update the maximum/minimum value.

Exit: The element at index i-k+1 leaves the window, update relevant statistics.

LC 1456 LC 1052 Grumpy Bookstore Owner: Answer = number of customers during all non-grumpy times + number of grumpy customers within the window.

1297. Maximum Number of Occurrences of a Substring ✨

High-frequency problem, greedy approach.

Variable-size Sliding Window

LC 2779

Shortest Window

If the condition is met, update the answer first in the while loop, and then pop the left side.

LC 219 Template Problem

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

def minSubArrayLen(self, target: int, nums: List[int]) -> int:
    s,l=0,0
    res=inf
    for r, x in enumerate(nums):
        s+=x
        while s>=target:
            res=min(res, r-l+1)
            s-=nums[l]
            l+=1
    return res if res<inf else 0

🌟If the condition for this problem changes to s==target to update the answer, this method has limitations because it will have issues when target=0.

So, prioritize the following writing style:

1
2
3
4
5

while cur>target_r:
    cur-=nums[l]
    l+=1
if cur==target_r:
        res=min(res, i-l+1)

2904. Shortest and Lexicographically Smallest Beautiful Substring

Purpose of the while loop: to minimize the length of the answer. Lexicographically smallest: directly compare the size of two strings.

76. Minimum Window Substring 🌟

Optimal solution.

1234. Replace the Substring for Balanced String

If it’s hard to solve directly, try the opposite.

Longest Window

Window can have at most two different elements / can change at most k elements, find the longest substring.

Add the right side first. If the condition is not met, continuously pop the left side in the while loop to get a valid substring, then update res.

LC 2024 LC 2779 1658. Minimum Operations to Reduce X to Zero: Reverse thinking. LC 3

Similar problem to LC3: What is the minimum number of parts a string needs to be divided into, such that each part has no duplicate characters?

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

def soln(password: str) -> int:
    count = 1
    seen = set()

    for i in range(len(password)):
        c = password[i]
        if c in seen:
            seen = {c}
            count += 1
        else:
            seen.add(c)

    print(count)
    return count

1438. Longest Continuous Subarray With Absolute Diff Less Than or Equal to Limit 🌟

Use two queues specifically to store the maximum and minimum values in the current window.

The maximum value queue is monotonically decreasing because when a new larger value is encountered, previous elements need to be popped from the tail of the queue.

Count Subarrays - Shorter is More Valid

713. Subarray Product Less Than K

Longer is More Valid

Generally, write ans += left.

After the inner loop ends, the subarray [left, right] does not satisfy the problem requirements, but in the last iteration before exiting the loop, [left-1, right] satisfies the problem requirements.

Count Subarrays - Exact Type

930. Binary Subarrays With Sum

Combine two sliding windows, maintaining the same right endpoint right and two left endpoints left1 and left2. left1 is on the left, meaning it exactly meets the condition. left2 is on the right, meaning it just doesn’t meet the condition.