题目要求
类型 1： 给定两个字符串 s 和 t，找满足某种变化规律的字串/最大字串/最大字串长度等。
类型 2：给定字符串 s，查找满足某种条件的最大/最小窗口。
解题模板
1
2
3
4
5
6
7
8
9
10
11
12
| class Solution:
def slidingWindowTemplate(s, t):
begin = end = 0
while f():
end += 1
while g():
begin += 1
|
模版变形：
- 前后指针同步移动可以简化为一层循环
- exactly(K) = atMost(K) - atMost(K-1)
案例应用
案例 1： Leetcode 424
Medium: Longest Repeating Character Replacement
给定一个字符串 s 和整数 k，求 s 变换 k 次后得到的最长重复子串是多长。其中变换规律是：每次操作可以将一个字符变化成任意字符。重复字符串是指所有字符都相同的字符串。
end 每次滑动要做啥：
累计 s[end] 出现的次数。如果 s[end] 出现次数大于了窗口中最大重复次数，则更新最大重复次数。如果窗口长度大于 k + max_count 则需要移动 begin 指针。
begin 指针移动要做啥：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| class Solution:
def characterReplacement(self, s: str, k: int) -> int:
if not s:
return 0
begin = end = 0
map = collections.defaultdict(int)
max_count = max_len = 0
while end < len(s):
c = s[end]
map[c] += 1
max_count = max(max_count, map[c])
end += 1
while end - begin > k + max_count:
b = s[begin]
map[b] -= 1
begin += 1
max_len = max(max_len, end - begin)
return max_len
|
案例 2：Max Consecutive Ones III
Medium: https://leetcode.com/problems/max-consecutive-ones-iii/solution/
给定一个只有 0 和 1 的数组 A 和一个操作次数 K，每次操作可以从 0 变成 1，求在 k 次操作下最大子数组的长度。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| class Solution:
def longestOnes(self, A: List[int], k: int) -> int:
begin = end = 0
max_len = 0
nums_one = 0
while end < len(A):
if A[end] == 1:
nums_one += 1
end += 1
while end - begin > nums_one + k:
if A[begin] == 1:
nums_one -= 1
begin += 1
max_len = max(max_len, end - begin)
return max_len
|
案例 3：Grumpy Bookstore Owner
Medium: https://leetcode.com/problems/grumpy-bookstore-owner/
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| class Solution:
def maxSatisfied(self, cus: List[int], gru: List[int], x: int) -> int:
init_sum = max_sum = 0
n = len(cus)
for i in range(n):
if gru[i] == 0:
init_sum += cus[i]
begin = end = 0
while end < n:
if gru[end] == 1:
init_sum += cus[end]
while end - begin == x:
if gru[begin] == 1:
init_sum -= cus[begin]
begin += 1
max_sum = max(max_sum, init_sum)
end += 1
return max_sum
|
案例 4： Longest Substring Without Repeating Characters
Medium: https://leetcode.com/problems/longest-substring-without-repeating-characters/
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
| class Solution:
def lengthOfLongestSubstring(self, s: str) -> int:
map = collections.defaultdict(int)
counter = 0
begin = end = 0
max_len = 0
while end < len(s):
e = s[end]
map[e] += 1
if map[e] > 1:
counter += 1
end += 1
while counter > 0:
b = s[begin]
if map[b] > 1:
counter -= 1
map[b] -= 1
begin += 1
max_len = max(max_len, end - begin)
return max_len
|
案例 5： Get Equal Substrings Within Budget
Medium: https://leetcode.com/problems/get-equal-substrings-within-budget/
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| class Solution:
def equalSubstring(self, s: str, t: str, cost: int) -> int:
begin = end = 0
max_len = 0
while end < len(s):
cost -= abs(ord(s[end]) - ord(t[end]))
end += 1
while cost < 0:
cost += abs(ord(s[begin]) - ord(t[begin]))
begin += 1
max_len = max(end - begin, max_len)
return max_len
|
案例 6：Permutation in String
Medium: https://leetcode.com/problems/permutation-in-string/
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
| class Solution:
def checkInclusion(self, s1: str, s2: str) -> bool:
d = collections.Counter(s1)
counter = len(d)
begin = end = 0
while end < len(s2):
e = s2[end]
if e in d:
d[e] -= 1
if d[e] == 0:
counter -= 1
end += 1
while counter == 0:
b = s2[begin]
if b in d:
d[b] += 1
if d[b] > 0:
counter += 1
if end - begin == len(s1):
return True
begin += 1
return False
|
案例 7： Minimum Window Substring
https://leetcode.com/problems/minimum-window-substring/
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
| class Solution:
def minWindow(self, s: str, t: str) -> str:
map = collections.Counter(t)
found = False
begin = end = 0
counter = len(map)
start = 0
min_len = len(s)
while end < len(s):
e = s[end]
if e in map:
map[e] -= 1
if map[e] == 0:
counter -= 1
end += 1
while counter == 0:
found = True
b = s[begin]
if b in map:
map[b] += 1
if map[b] > 0:
counter += 1
if end - begin < min_len:
min_len = end - begin
start = begin
begin += 1
return s[start: start + min_len] if found else ""
|