# 滑动窗口解题套路框架

Info

**已完成网站教程、网站习题、配套插件中所有多语言代码的校准，解决了之前 chatGPT 翻译可能出错的问题~**

读完本文，你不仅学会了算法套路，还可以顺便解决如下题目：

LeetCode | Difficulty |
---|---|

3. Longest Substring Without Repeating Characters | 🟠 |

438. Find All Anagrams in a String | 🟠 |

567. Permutation in String | 🟠 |

76. Minimum Window Substring | 🔴 |

Tip

本文有视频版：滑动窗口算法核心模板框架。建议关注我的 B 站账号，我会用视频领读的方式带大家学习那些稍有难度的算法技巧。

Given the positive reception of the poem "Binary Search Ascension" from the previous article Binary Search Framework Detailed Explanation, which has become widely circulated and even used as a sleep aid, today I've written another poem to celebrate the greatness of the sliding window algorithm within the sliding window framework (wink):

Haha, I'm almost praising myself to the skies! Just take it as a bit of fun, don't take it too seriously. 😃

For the usage of fast and slow pointers, as well as left and right pointers in the two-pointer technique, you can refer to the previous article Two-Pointer Technique Summary. In this article, we'll tackle the most challenging aspect of the two-pointer technique: the sliding window technique. I'll also provide a framework that ensures you can write correct solutions even with your eyes closed.

## Overview of Sliding Window Framework

**The sliding window algorithm technique is mainly used to solve subarray problems, such as finding the longest/shortest subarray that meets certain conditions**.

If you use a brute-force approach, you need to use nested for loops to enumerate all subarrays, resulting in a time complexity of `O(N^2)`

:

```
for (int i = 0; i < nums.length; i++) {
for (int j = i; j < nums.length; j++) {
// nums[i, j] is a subarray
}
}
```

The idea behind the sliding window algorithm technique is not difficult. It involves maintaining a window that slides continuously, and then updating the answer. The general logic of this algorithm is as follows:

```
int left = 0, right = 0;
while (right < nums.size()) {
// expand the window
window.addLast(nums[right]);
right++;
while (window needs shrink) {
// shrink the window
window.removeFirst(nums[left]);
left++;
}
}
```

The code based on the sliding window algorithm framework has a time complexity of `O(N)`

, which is more efficient than the brute-force solution using nested for loops.

Why is it `O(N)`?

Some readers might wonder, doesn't this sliding window framework also use a nested while loop? Why is the complexity `O(N)`

?

Simply put, the pointers `left`

and `right`

do not retreat (their values only increase), so each element in the string/array will only enter the window once and then be removed once. There are no elements that enter and leave the window multiple times, so the time complexity of the algorithm is directly proportional to the length of the string/array.

In contrast, the brute-force solution with nested for loops has the `j`

pointer retreating, causing some elements to enter and leave the window multiple times, resulting in a time complexity of `O(N^2)`

.

I have a detailed guide on how to theoretically estimate time and space complexity in A Practical Guide to Algorithm Time and Space Complexity Analysis, but I won't elaborate here.

Why can the sliding window enumerate subarrays in `O(N)` time?

This question itself is misleading. **The sliding window cannot enumerate all substrings**. To enumerate all substrings, you must use the nested for loop.

However, for some problems, you don't need to enumerate all substrings to find the desired answer. The sliding window is an algorithm template for such scenarios, helping you prune the enumeration process and avoid redundant calculations.

Therefore, in The Essence of Algorithms, I classify the sliding window algorithm as a method for "how to enumerate smartly."

Actually, what困扰s most people is not the algorithm's思路 but the various细节 issues. For example, how to add new elements to the window, how to shrink the window, and at which stage of the window sliding to update the result. Even if you understand these details, your code can still have bugs, and finding bugs can be frustrating.

**So today, I will provide a sliding window algorithm code framework, including debug output points. For future related problems, you can simply write out this framework and modify three places, ensuring no bugs**.

Since most of the examples in this article are substring-related problems, and strings are essentially arrays, I will set the input as a string. You can adapt it based on the specific problem you are solving:

```
// Pseudocode framework of sliding window algorithm
void slidingWindow(String s) {
// Use an appropriate data structure to record the data in the window, which can vary according to the specific scenario
// For example, if I want to record the frequency of elements in the window, I would use a map
// If I want to record the sum of elements in the window, I could just use an int
Object window = ...
int left = 0, right = 0;
while (right < s.length()) {
// c is the character that will be added to the window
char c = s[right];
window.add(c)
// Expand the window
right++;
// Perform a series of updates to the data within the window
...
// *** Position of debug output ***
// Note that in the final solution code, do not use print
// Because IO operations are time-consuming and may cause timeouts
printf("window: [%d, %d)\n", left, right);
// ***********************
// Determine whether the left side of the window needs to shrink
while (left < right && window needs shrink) {
// d is the character that will be removed from the window
char d = s[left];
window.remove(d)
// Shrink the window
left++;
// Perform a series of updates to the data within the window
...
}
}
}
```

```
// Pseudocode framework of sliding window algorithm
void slidingWindow(string s) {
// Use an appropriate data structure to record the data in the window, varying with the specific scenario
// For instance, if I want to record the frequency of elements in the window, I would use a map
// If I want to record the sum of elements in the window, I can simply use an int
auto window = ...
int left = 0, right = 0;
while (right < s.size()) {
// c is the character that will be entering the window
char c = s[right];
window.add(c);
// Expand the window
right++;
// Perform a series of updates to the data within the window
...
// *** position of debug output ***
printf("window: [%d, %d)\n", left, right);
// Note that printing should be avoided in the final solution code
// Because IO operations are time-consuming and may cause timeouts
// Determine whether the left side of the window needs to shrink
while (window needs shrink) {
// d is the character that will be removed from the window
char d = s[left];
window.remove(d);
// Shrink the window
left++;
// Perform a series of updates to the data within the window
...
}
}
}
```

```
# Pseudocode framework for sliding window algorithm
def slidingWindow(s: str):
# Use an appropriate data structure to record the data in the window, which can vary depending on the scenario
# For example, if I want to record the frequency of elements in the window, I would use a map
# If I want to record the sum of elements in the window, I could just use an int
window = ...
left, right = 0, 0
while right < len(s):
# c is the character that will be added to the window
c = s[right]
window.add(c)
# Expand the window
right += 1
# Perform a series of updates on the data within the window
...
# *** position for debug output ***
# Note that you should not print in the final solution code
# because IO operations are time-consuming and may cause timeouts
# print(f"window: [{left}, {right})")
# ***********************
# Determine whether the left side of the window needs to be contracted
while left < right and window needs shrink:
# d is the character that will be removed from the window
d = s[left]
window.remove(d)
# Shrink the window
left += 1
# Perform a series of updates on the data within the window
...
```

```
// Pseudocode framework for sliding window algorithm
func slidingWindow(s string) {
// Use an appropriate data structure to record the data in the window, which can vary according to the specific scenario
// For example, if I want to record the frequency of elements in the window, I use a map
// If I want to record the sum of elements in the window, I can just use an int
var window = ...
left, right := 0, 0
for right < len(s) {
// c is the character to be moved into the window
c := rune(s[right])
window[c]++
// Expand the window
right++
// Perform a series of updates to the data within the window
...
// *** debug output location ***
// Note that in the final solution code, do not print
// Because IO operations are time-consuming and may cause timeouts
fmt.Println("window: [",left,", ",right,")")
// ***********************
// Determine whether the left window needs to shrink
for left < right && window needs shrink { //replace "window needs shrink" with actual condition
// d is the character to be moved out of the window
d := rune(s[left])
window[d]--
// Shrink the window
left++
// Perform a series of updates to the data within the window
...
}
}
}
```

```
// Pseudocode framework for sliding window algorithm
var slidingWindow = function(s) {
// Use an appropriate data structure to record the data in the window, which can vary according to the scenario
// For example, if I want to record the frequency of elements in the window, I use a map
// If I want to record the sum of the elements in the window, I can just use an int
var window = ...;
var left = 0, right = 0;
while (right < s.length) {
// c is the character that will be moved into the window
var c = s[right];
window.add(c);
// Expand the window
right++;
// Perform a series of updates on the data within the window
...
// *** debug output position ***
// Note that in the final solution code, do not print
// Because IO operations are time-consuming and may cause timeouts
console.log("window: [%d, %d)\n", left, right);
// *********************
// Determine whether the left side of the window needs to shrink
while (window needs shrink) {
// d is the character that will be moved out of the window
var d = s[left];
window.remove(d);
// Shrink the window
left++;
// Perform a series of updates on the data within the window
...
}
}
};
```

**In the framework, the two places marked with ... represent where you need to update the window data. Your task in specific problems is to fill in the code logic here**. Moreover, the operations at these two

`...`

places are for expanding and shrinking the window, respectively, and you will find that they are completely symmetric.As a side note, some readers have commented on this framework, suggesting that hash tables are slow and should be replaced with arrays. Others prefer writing very concise code, claiming that my approach is too verbose and not fast enough. My view is that algorithms should primarily be judged by their time complexity. As long as you can ensure optimal time complexity, that's what matters. Regarding LeetCode's execution speed, it can be a bit unpredictable. As long as your solution isn't ridiculously slow, it's fine. There's no need to optimize at the compilation level and miss the forest for the trees...

Furthermore, the focus of my algorithm tutorials is on the algorithmic thinking. First, master the framework mindset, and then feel free to modify the code as you like. This ensures that you can write correct solutions no matter how you implement them.

Getting back on topic, let's apply this framework to four original LeetCode problems. I will explain the principles in detail for the first problem, and then you can solve the remaining three problems almost effortlessly.

## 1. Minimum Window Substring

Let's start with LeetCode problem #76, "Minimum Window Substring," which is classified as Hard:

**76. Minimum Window Substring** | 力扣 | LeetCode |

Given two strings `s`

and `t`

of lengths `m`

and `n`

respectively, return *the minimum window*

*substring**of*

`s`

*such that every character in*

`t`

*(*. If there is no such substring, return

**including duplicates**) is included in the window*the empty string*

`""`

.The testcases will be generated such that the answer is **unique**.

**Example 1:**

Input:s = "ADOBECODEBANC", t = "ABC"Output:"BANC"Explanation:The minimum window substring "BANC" includes 'A', 'B', and 'C' from string t.

**Example 2:**

Input:s = "a", t = "a"Output:"a"Explanation:The entire string s is the minimum window.

**Example 3:**

Input:s = "a", t = "aa"Output:""Explanation:Both 'a's from t must be included in the window. Since the largest window of s only has one 'a', return empty string.

**Constraints:**

`m == s.length`

`n == t.length`

`1 <= m, n <= 10`

^{5}`s`

and`t`

consist of uppercase and lowercase English letters.

**Follow up:** Could you find an algorithm that runs in `O(m + n)`

time?

The goal is to find a substring in `S`

(source) that contains all the characters from `T`

(target), and this substring must be the shortest among all possible substrings.

If we use a brute-force approach, the code would look something like this:

```
for (int i = 0; i < s.length(); i++)
for (int j = i + 1; j < s.length(); j++)
if s[i:j] 包含 t 的所有字母:
更新答案
```

The idea is straightforward, but obviously, the complexity of this algorithm is definitely greater than O(N^2), which is not good.

**The sliding window algorithm works like this**:

- We use two pointers, left and right, in the string
`S`

, initializing`left = right = 0`

. We call the index interval`[left, right)`

a "window."

Why use a "left-closed, right-open" interval

**Theoretically, you can design intervals that are open at both ends or closed at both ends, but a left-closed, right-open interval is the most convenient to handle**.

This is because when initialized as `left = right = 0`

, the interval `[0, 0)`

contains no elements. But as soon as you move `right`

one step to the right (expanding), the interval `[0, 1)`

includes one element, `0`

.

If you use an interval that is open at both ends, moving `right`

one step to the right still leaves the interval `(0, 1)`

empty. If you use an interval that is closed at both ends, the initial interval `[0, 0]`

already includes one element. Both scenarios create unnecessary boundary handling issues.

We continuously increase the

`right`

pointer to expand the window`[left, right)`

until the substring in the window meets the requirement (contains all characters in`T`

).At this point, we stop increasing

`right`

and start increasing the`left`

pointer to shrink the window`[left, right)`

until the substring no longer meets the requirement (does not contain all characters in`T`

). Each time we increase`left`

, we update the result.Repeat steps 2 and 3 until

`right`

reaches the end of the string`S`

.

This approach is not difficult. **Step 2 is like finding a "feasible solution," and step 3 is optimizing this "feasible solution" to find the optimal solution**, which is the shortest covering substring. The left and right pointers take turns moving forward, and the window size increases and decreases, resembling a caterpillar stretching and shrinking as it slides to the right. This is where the name "sliding window" comes from.

Let's visualize the process. `needs`

and `window`

act as counters, recording the frequency of characters in `T`

and the corresponding characters in the "window," respectively.

Initial state:

Increase `right`

until the window `[left, right)`

contains all characters from `T`

:

Now, start increasing `left`

to shrink the window `[left, right)`

:

Continue until the string in the window no longer meets the requirements, and `left`

stops moving:

Repeat the above process: move `right`

first, then `left`

... until the `right`

pointer reaches the end of string `S`

, at which point the algorithm ends.

If you understand this process, congratulations! You've fully grasped the sliding window algorithm concept. **Now let's see how to use this sliding window code framework**:

First, initialize two hash tables, `window`

and `need`

, to record the characters in the window and the characters needed to complete the set:

```
// Record the frequency of characters in the window
HashMap<Character, Integer> window = new HashMap<>();
// Record the frequency of characters needed
HashMap<Character, Integer> need = new HashMap<>();
for (int i = 0; i < t.length(); i++) {
char c = t.charAt(i);
need.put(c, need.getOrDefault(c, 0) + 1);
}
```

Next, initialize the two ends of the window using the `left`

and `right`

variables. Don't forget, the interval `[left, right)`

is left-closed and right-open, so initially, the window does not contain any elements:

```
int left = 0, right = 0;
int valid = 0;
while (right < s.length()) {
// c is the character to be added into the window
char c = s.charAt(right);
// move the window to the right
right++;
// perform a series of updates to the data within the window
...
}
```

**The valid variable represents the number of characters in the window that meet the need conditions.** If

`valid`

is equal to `need.size`

, it means the window satisfies the conditions and completely covers the string `T`

.**Now, let's apply the template. You only need to think about the following questions**:

When should we move

`right`

to expand the window? What data should be updated when a character is added to the window?When should the window stop expanding and start moving

`left`

to shrink? What data should be updated when a character is removed from the window?When should we update our final result: during window expansion or contraction?

If a character enters the window, the `window`

counter should be increased; if a character is about to leave the window, the `window`

counter should be decreased; when `valid`

meets `need`

, the window should be contracted; and the final result should be updated during window contraction.

Here is the complete code:

```
class Solution {
public String minWindow(String s, String t) {
Map<Character, Integer> need = new HashMap<>();
Map<Character, Integer> window = new HashMap<>();
for (char c : t.toCharArray()) {
need.put(c, need.getOrDefault(c, 0) + 1);
}
int left = 0, right = 0;
int valid = 0;
// record the start index and length of the minimum coverage substring
int start = 0, len = Integer.MAX_VALUE;
while (right < s.length()) {
// c is the character that will be added to the window
char c = s.charAt(right);
// expand the window
right++;
// perform a series of updates to the data inside the window
if (need.containsKey(c)) {
window.put(c, window.getOrDefault(c, 0) + 1);
if (window.get(c).equals(need.get(c)))
valid++;
}
// determine whether the left side of the window needs to be contracted
while (valid == need.size()) {
// update the minimum coverage substring here
if (right - left < len) {
start = left;
len = right - left;
}
// d is the character that will be removed from the window
char d = s.charAt(left);
// shrink the window
left++;
// perform a series of updates to the data inside the window
if (need.containsKey(d)) {
if (window.get(d).equals(need.get(d)))
valid--;
window.put(d, window.get(d) - 1);
}
}
}
// return the minimum coverage substring
return len == Integer.MAX_VALUE ? "" : s.substring(start, start + len);
}
}
```

```
class Solution {
public:
string minWindow(string s, string t) {
unordered_map<char, int> need, window;
for (char c : t) {
need[c]++;
}
int left = 0, right = 0;
// record the number of characters in window that meet the need condition
int valid = 0;
// record the start index and length of the minimum covering substring
int start = 0, len = INT_MAX;
while (right < s.size()) {
// c is the character to be moved into the window
char c = s[right];
// expand the window
right++;
// perform a series of updates to the data within the window
if (need.count(c)) {
window[c]++;
if (window[c] == need[c])
valid++;
}
// determine whether the left window needs to be shrinked
while (valid == need.size()) {
// update the minimum covering substring here
if (right - left < len) {
start = left;
len = right - left;
}
// d is the character to be moved out of the window
char d = s[left];
// shrink the window
left++;
// perform a series of updates to the data within the window
if (need.count(d)) {
if (window[d] == need[d])
valid--;
window[d]--;
}
}
}
// return the minimum covering substring
return len == INT_MAX ? "" : s.substr(start, len);
}
};
```

```
class Solution:
def minWindow(self, s: str, t: str) -> str:
need, window = {}, {}
for c in t:
need[c] = need.get(c, 0) + 1
left = 0
right = 0
valid = 0
# record the start index and length of the minimum covering substring
start = 0
length = float('inf')
while right < len(s):
# c is the character that will be added to the window
c = s[right]
# expand the window
right += 1
# perform a series of updates to the data within the window
if c in need:
window[c] = window.get(c, 0) + 1
if window[c] == need[c]:
valid += 1
# determine whether the left side of the window needs to be contracted
while valid == len(need):
# update the minimum covering substring here
if right - left < length:
start = left
length = right - left
# d is the character that will be removed from the window
d = s[left]
# shrink the window
left += 1
# perform a series of updates to the data within the window
if d in need:
if window[d] == need[d]:
valid -= 1
window[d] -= 1
# return the minimum covering substring
return "" if length == float('inf') else s[start: start + length]
```

```
func minWindow(s string, t string) string {
need, window := make(map[byte]int), make(map[byte]int)
for i := range t {
need[t[i]]++
}
left, right := 0, 0
valid := 0
// record the start index and length of the minimum covering substring
start, length := 0, math.MaxInt32
for right < len(s) {
// c is the character that will be added to the window
c := s[right]
// expand the window
right++
// perform a series of updates to the data inside the window
if _, ok := need[c]; ok {
window[c]++
if window[c] == need[c] {
valid++
}
}
// determine whether the left side of the window needs to be contracted
for valid == len(need) {
// update the minimum covering substring here
if right - left < length {
start = left
length = right - left
}
// d is the character that will be removed from the window
d := s[left]
// shrink the window
left++
// perform a series of updates to the data inside the window
if _, ok := need[d]; ok {
if window[d] == need[d] {
valid--
}
window[d]--
}
}
}
// return the minimum covering substring
if length == math.MaxInt32 {
return ""
}
return s[start : start+length]
}
```

```
var minWindow = function(s, t) {
let need = {}, window = {};
for (let c of t) {
need[c] = (need[c] || 0) + 1;
}
let left = 0, right = 0;
let valid = 0;
// record the start index and length of the minimum covering substring
let start = 0, len = Infinity;
while (right < s.length) {
// c is the character to be moved into the window
let c = s[right];
// expand the window
right++;
// perform a series of updates to the data inside the window
if (need[c]) {
window[c] = (window[c] || 0) + 1;
if (window[c] === need[c]) {
valid++;
}
}
// determine whether the left side of the window needs to shrink
while (valid === Object.keys(need).length) {
// update the minimum covering substring here
if (right - left < len) {
start = left;
len = right - left;
}
// d is the character to be moved out of the window
let d = s[left];
// shrink the window
left++;
// perform a series of updates to the data inside the window
if (need[d]) {
if (window[d] === need[d]) {
valid--;
}
window[d]--;
}
}
}
// return the minimum covering substring
return len === Infinity ? "" : s.substring(start, start + len);
};
```

Note for Java Users

Be extra cautious when comparing Java wrapper classes like `Integer`

and `String`

. You should use the `equals`

method to check for equality, not the direct equality operator `==`

, as it can lead to errors. Therefore, when updating the window data, avoid writing `window.get(d) == need.get(d)`

. Instead, use `window.get(d).equals(need.get(d))`

. The same applies to the code in subsequent problems.

In the code above, when we find that the count of a character in `window`

meets the requirement of `need`

, we update `valid`

to indicate that one character has satisfied the condition. You'll notice that the two updates to the window data are completely symmetrical.

When `valid == need.size()`

, it means all characters in `T`

are covered, and we have a valid substring. Now, we should start shrinking the window to find the "minimum covering substring."

As we move `left`

to shrink the window, all characters within the window are part of the feasible solution. Therefore, we should update the minimum covering substring during this phase to find the shortest possible result from the feasible solutions.

By now, you should fully understand this framework. The sliding window algorithm isn't difficult; it's just the details that can be annoying. **In the future, whenever you encounter a sliding window problem, just follow this framework to write your code. It's guaranteed to be bug-free and saves you trouble.**

Let's apply this framework to solve a few problems. You'll basically see the solution at a glance.

## 2. String Permutations

This is LeetCode problem #567, "Permutation in String," with a medium difficulty level:

**567. Permutation in String** | 力扣 | LeetCode |

Given two strings `s1`

and `s2`

, return `true`

* if *`s2`

* contains a permutation of *`s1`

*, or *`false`

* otherwise*.

In other words, return `true`

if one of `s1`

's permutations is the substring of `s2`

.

**Example 1:**

Input:s1 = "ab", s2 = "eidbaooo"Output:trueExplanation:s2 contains one permutation of s1 ("ba").

**Example 2:**

Input:s1 = "ab", s2 = "eidboaoo"Output:false

**Constraints:**

`1 <= s1.length, s2.length <= 10`

^{4}`s1`

and`s2`

consist of lowercase English letters.

Note that the input `s1`

can contain duplicate characters, which makes this problem quite challenging.

This type of problem is a classic example of the sliding window algorithm. **Essentially, you are given a string S and a string T. The question is whether there exists a substring in S that contains all characters of T and no other characters**?

First, start by copying and pasting the previous algorithm framework code. Then, clarify the questions raised earlier, and you can write the solution to this problem:

```
class Solution {
// determine if there is a permutation of t in s
public boolean checkInclusion(String t, String s) {
Map<Character, Integer> need = new HashMap<>();
Map<Character, Integer> window = new HashMap<>();
for (char c : t.toCharArray()) {
need.put(c, need.getOrDefault(c, 0) + 1);
}
int left = 0, right = 0;
int valid = 0;
while (right < s.length()) {
char c = s.charAt(right);
right++;
// perform a series of updates to the data within the window
if (need.containsKey(c)) {
window.put(c, window.getOrDefault(c, 0) + 1);
if (window.get(c).intValue() == need.get(c).intValue())
valid++;
}
// determine if the left side of the window needs to shrink
while (right - left >= t.length()) {
// determine if a valid substring is found here
if (valid == need.size())
return true;
char d = s.charAt(left);
left++;
// perform a series of updates to the data within the window
if (need.containsKey(d)) {
if (window.get(d).intValue() == need.get(d).intValue())
valid--;
window.put(d, window.get(d) - 1);
}
}
}
// no substring meeting the conditions was found
return false;
}
}
```

```
class Solution {
public:
// determine if there is a permutation of t in s
bool checkInclusion(string t, string s) {
unordered_map<char, int> need, window;
for (char c : t) {
need[c]++;
}
int left = 0, right = 0;
int valid = 0;
while (right < s.size()) {
char c = s[right];
right++;
// perform a series of updates to the data within the window
if (need.count(c)) {
window[c]++;
if (window[c] == need[c])
valid++;
}
// determine if the left side of the window should shrink
while (right - left >= t.size()) {
// here, determine if a valid substring is found
if (valid == need.size())
return true;
char d = s[left];
left++;
// perform a series of updates to the data within the window
if (need.count(d)) {
if (window[d] == need[d])
valid--;
window[d]--;
}
}
}
// no substring meeting the criteria was found
return false;
}
};
```

```
class Solution:
# determine if there is a permutation of t in s
def checkInclusion(self, t: str, s: str) -> bool:
need, window = collections.defaultdict(int), collections.defaultdict(int)
for c in t:
need[c] += 1
left, right, valid = 0, 0, 0
while right < len(s):
c = s[right]
right += 1
# perform a series of updates within the window
if c in need:
window[c] += 1
if window[c] == need[c]:
valid += 1
# determine if the left window needs to shrink
while (right - left >= len(t)):
# here determine if a valid substring is found
if valid == len(need):
return True
d = s[left]
left += 1
# perform a series of updates within the window
if d in need:
if window[d] == need[d]:
valid -= 1
window[d] -= 1
# no valid substring found
return False
```

```
// Determine if there is a permutation of t in s
func checkInclusion(t string, s string) bool {
need := make(map[rune]int)
window := make(map[rune]int)
for _, c := range t {
need[c]++
}
left, right := 0, 0
valid := 0
for right < len(s) {
c := rune(s[right])
right++
// Perform a series of updates within the window
if _, ok := need[c]; ok {
window[c]++
if window[c] == need[c] {
valid++
}
}
// Determine if the left window needs to shrink
for right - left >= len(t) {
// Here, determine if a valid substring has been found
if valid == len(need) {
return true
}
d := rune(s[left])
left++
// Perform a series of updates within the window
if _, ok := need[d]; ok {
if window[d] == need[d] {
valid--
}
window[d]--
}
}
}
// No substring meeting the conditions was found
return false
}
```

```
var checkInclusion = function(t, s){
var need = new Map();
var window = new Map();
for (var c of t) {
need.set(c, (need.get(c) || 0) + 1);
}
var left = 0, right = 0;
var valid = 0;
while (right < s.length) {
var c = s[right];
right++;
// perform a series of updates within the window
if (need.has(c)) {
window.set(c, (window.get(c) || 0) + 1);
if (window.get(c) === need.get(c))
valid++;
}
// determine whether the left side of the window needs to shrink
while (right - left >= t.length) {
// here determine if a valid substring is found
if (valid === need.size)
return true;
var d = s[left];
left++;
// perform a series of updates within the window
if (need.has(d)) {
if (window.get(d) === need.get(d))
valid--;
window.set(d, window.get(d) - 1);
}
}
}
// no substring found that meets the criteria
return false;
};
```

The solution code for this problem is almost identical to the minimum window substring problem, with just a few changes:

In this problem, we move

`left`

to shrink the window when the window size is greater than`t.length()`

. This is because, for a permutation, the lengths should obviously be the same.When

`valid == need.size()`

, it means the window contains a valid permutation, so we immediately return`true`

.

The handling of expanding and shrinking the window is exactly the same as in the minimum window substring problem.

Optimization

Since in this problem, `[left, right)`

actually maintains a **fixed-length** window with a length of `t.length()`

. Because a fixed-length window only removes one character each time it slides forward, we can change the inner `while`

loop to an `if`

statement, achieving the same effect.

## III. Finding All Anagrams in a String

This is LeetCode problem #438, "Find All Anagrams in a String," with a medium difficulty level:

**438. Find All Anagrams in a String** | 力扣 | LeetCode |

Given two strings `s`

and `p`

, return *an array of all the start indices of *`p`

*'s anagrams in *`s`

. You may return the answer in **any order**.

An **Anagram** is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once.

**Example 1:**

Input:s = "cbaebabacd", p = "abc"Output:[0,6]Explanation:The substring with start index = 0 is "cba", which is an anagram of "abc". The substring with start index = 6 is "bac", which is an anagram of "abc".

**Example 2:**

Input:s = "abab", p = "ab"Output:[0,1,2]Explanation:The substring with start index = 0 is "ab", which is an anagram of "ab". The substring with start index = 1 is "ba", which is an anagram of "ab". The substring with start index = 2 is "ab", which is an anagram of "ab".

**Constraints:**

`1 <= s.length, p.length <= 3 * 10`

^{4}`s`

and`p`

consist of lowercase English letters.

Oh, this so-called letter anagram is just a permutation, right? Can a fancy term really fool people? **In essence, you are given a string S and a string T. Your task is to find all permutations of T within S and return their starting indices.**

Simply recall the framework discussed earlier, clarify the four key points, and you can solve this problem in no time:

```
class Solution {
public List<Integer> findAnagrams(String s, String t) {
Map<Character, Integer> need = new HashMap<>();
Map<Character, Integer> window = new HashMap<>();
for (char c : t.toCharArray()) {
need.put(c, need.getOrDefault(c, 0) + 1);
}
int left = 0, right = 0;
int valid = 0;
// record the result
List<Integer> res = new ArrayList<>();
while (right < s.length()) {
char c = s.charAt(right);
right++;
// perform a series of updates to the data within the window
if (need.containsKey(c)) {
window.put(c, window.getOrDefault(c, 0) + 1);
if (window.get(c).equals(need.get(c))) {
valid++;
}
}
// determine whether the left side of the window needs to shrink
while (right - left >= t.length()) {
// when the window meets the condition, add the starting index to res
if (valid == need.size())
res.add(left);
char d = s.charAt(left);
left++;
// perform a series of updates to the data within the window
if (need.containsKey(d)) {
if (window.get(d).equals(need.get(d))) {
valid--;
}
window.put(d, window.get(d) - 1);
}
}
}
return res;
}
}
```

```
class Solution {
public:
vector<int> findAnagrams(string s, string t) {
unordered_map<char, int> need, window;
for (char c : t) {
need[c]++;
}
int left = 0, right = 0;
int valid = 0;
// record the result
vector<int> res;
while (right < s.size()) {
char c = s[right];
right++;
// perform a series of updates to the data within the window
if (need.count(c)) {
window[c]++;
if (window[c] == need[c]) {
valid++;
}
}
// determine whether the left window needs to shrink
while (right - left >= t.size()) {
// when the window meets the condition, add the starting index to res
if (valid == need.size())
res.push_back(left);
char d = s[left];
left++;
// perform a series of updates to the data within the window
if (need.count(d)) {
if (window[d] == need[d]) {
valid--;
}
window[d]--;
}
}
}
return res;
}
};
```

```
class Solution:
def findAnagrams(self, s: str, t: str) -> List[int]:
need = {}
window = {}
for c in t:
need[c] = need.get(c, 0) + 1
left = 0
right = 0
valid = 0
# record the result
res = []
while right < len(s):
c = s[right]
right += 1
# perform a series of updates to the data within the window
if c in need:
window[c] = window.get(c, 0) + 1
if window[c] == need[c]:
valid += 1
# determine whether the left side of the window should shrink
while right - left >= len(t):
# when the window meets the condition, add the starting index to res
if valid == len(need):
res.append(left)
d = s[left]
left += 1
# perform a series of updates to the data within the window
if d in need:
if window[d] == need[d]:
valid -= 1
window[d] -= 1
return res
```

```
func findAnagrams(s string, t string) []int {
need, window := make(map[rune]int), make(map[rune]int)
for _, c := range t {
need[c]++
}
left, right := 0, 0
valid := 0
// record the result
var res []int
for right < len(s) {
c := rune(s[right])
right++
// perform a series of updates within the window
if _, ok := need[c]; ok {
window[c]++
if window[c] == need[c] {
valid++
}
}
// determine whether the left window needs to shrink
for right - left >= len(t) {
// when the window meets the condition, add the starting index to res
if valid == len(need) {
res = append(res, left)
}
d := rune(s[left])
left++
// perform a series of updates within the window
if _, ok := need[d]; ok {
if window[d] == need[d] {
valid--
}
window[d]--
}
}
}
return res
}
```

```
var findAnagrams = function(s, t) {
let need = {};
let window = {};
for (let c of t) {
need[c] = (need[c] || 0) + 1;
}
let left = 0, right = 0;
let valid = 0;
// record the result
let res = [];
while (right < s.length) {
let c = s[right];
right++;
// perform a series of updates to the data within the window
if (need[c] !== undefined) {
window[c] = (window[c] || 0) + 1;
if (window[c] === need[c]) {
valid++;
}
}
// determine whether the left side of the window needs to shrink
while (right - left >= t.length) {
// when the window meets the condition, add the starting index to res
if (valid === Object.keys(need).length)
res.push(left);
let d = s[left];
left++;
// perform a series of updates to the data within the window
if (need[d] !== undefined) {
if (window[d] === need[d]) {
valid--;
}
window[d] = window[d] - 1;
}
}
}
return res;
};
```

Just like finding permutations of a string, once a valid anagram (permutation) is found, simply add the starting index to `res`

.

## IV. Longest Substring Without Repeating Characters

This is LeetCode problem #3, "Longest Substring Without Repeating Characters," with a medium difficulty level:

**3. Longest Substring Without Repeating Characters** | 力扣 | LeetCode |

Given a string `s`

, find the length of the **longest** **substring** without repeating characters.

**Example 1:**

Input:s = "abcabcbb"Output:3Explanation:The answer is "abc", with the length of 3.

**Example 2:**

Input:s = "bbbbb"Output:1Explanation:The answer is "b", with the length of 1.

**Example 3:**

Input:s = "pwwkew"Output:3Explanation:The answer is "wke", with the length of 3. Notice that the answer must be a substring, "pwke" is a subsequence and not a substring.

**Constraints:**

`0 <= s.length <= 5 * 10`

^{4}`s`

consists of English letters, digits, symbols and spaces.

Finally, this problem offers something new. It's not just about fitting into a framework to get the answer. In fact, it's even simpler; just a slight modification to the framework will do:

```
class Solution {
public int lengthOfLongestSubstring(String s) {
Map<Character, Integer> window = new HashMap<>();
int left = 0, right = 0;
// record the result
int res = 0;
while (right < s.length()) {
char c = s.charAt(right);
right++;
// perform a series of updates to the data within the window
window.put(c, window.getOrDefault(c, 0) + 1);
// determine whether the left window needs to shrink
while (window.get(c) > 1) {
char d = s.charAt(left);
left++;
// perform a series of updates to the data within the window
window.put(d, window.get(d) - 1);
}
// update the answer here
res = Math.max(res, right - left);
}
return res;
}
}
```

```
class Solution {
public:
int lengthOfLongestSubstring(string s) {
unordered_map<char, int> window;
int left = 0, right = 0;
// record the result
int res = 0;
while (right < s.size()) {
char c = s[right];
right++;
// perform a series of updates to the data within the window
window[c]++;
// determine whether the left window needs to shrink
while (window[c] > 1) {
char d = s[left];
left++;
// perform a series of updates to the data within the window
window[d]--;
}
// update the answer here
res = max(res, right - left);
}
return res;
}
};
```

```
class Solution:
def lengthOfLongestSubstring(self, s: str) -> int:
window = {}
left, right = 0, 0
# record the result
res = 0
while right < len(s):
c = s[right]
right += 1
# perform a series of updates to the data within the window
window[c] = window.get(c, 0) + 1
# determine whether the left window needs to shrink
while window.get(c) > 1:
d = s[left]
left += 1
# perform a series of updates to the data within the window
window[d] -= 1
# update the answer here
res = max(res, right - left)
return res
```

```
func lengthOfLongestSubstring(s string) int {
window := make(map[rune]int)
left := 0
right := 0
// record the result
res := 0
for right < len(s) {
c := rune(s[right])
right++
// perform a series of updates to the data within the window
window[c] = window[c] + 1
// determine whether the left window needs to shrink
for window[c] > 1 {
d := rune(s[left])
left++
// perform a series of updates to the data within the window
window[d] = window[d] - 1
}
// update the answer here
if res < (right - left) {
res = right - left
}
}
return res
}
```

```
var lengthOfLongestSubstring = function(s) {
var window = {};
var left = 0, right = 0;
// record the result
var res = 0;
while (right < s.length) {
var c = s.charAt(right);
right++;
// update the data within the window
window[c] = (window[c] || 0) + 1;
// determine whether the left window needs to shrink
while (window[c] > 1) {
var d = s.charAt(left);
left++;
// update the data within the window
window[d] = window[d] - 1;
}
// update the answer here
res = Math.max(res, right - left);
}
return res;
};
```

This simplifies things, eliminating the need for `need`

and `valid`

, and updating the data within the window only requires a simple counter update `window`

.

When `window[c]`

is greater than 1, it indicates that there are duplicate characters in the window, which does not meet the condition. Thus, you should move `left`

to shrink the window.

The only thing to note is, where should you update the result `res`

? We want the longest substring without duplicates. At which stage can we ensure that the string in the window has no duplicates?

Here, it's different from before. You should update `res`

after the window shrinking is complete, because the while condition for shrinking the window is the presence of duplicate elements. In other words, once the shrinking is done, it guarantees that there are no duplicates in the window.

Alright, this concludes the sliding window algorithm template. I hope everyone can understand the underlying concept, remember the algorithm template, and apply it flexibly. To recap, when dealing with subarray/substring problems, as long as you can answer the following questions, you can apply the sliding window algorithm:

When should you expand the window?

When should you shrink the window?

When should you update the answer?

In Classic Sliding Window Exercises, I use this thinking model to list more classic exercises, aiming to strengthen your understanding and memory of the algorithm. This way, you won't be afraid of substring and subarray problems anymore.

**引用本文的题目**

**安装 我的 Chrome 刷题插件 点开下列题目可直接查看解题思路：**