不定长滑动窗口其他 Variable Sliding Window Others¶
Table of Contents¶
- 825. Friends Of Appropriate Ages (Medium)
- 2401. Longest Nice Subarray (Medium)
- 1156. Swap For Longest Repeated Character Substring (Medium)
- 424. Longest Repeating Character Replacement (Medium)
- 438. Find All Anagrams in a String (Medium)
- 1712. Ways to Split Array Into Three Subarrays (Medium)
- 1918. Kth Smallest Subarray Sum (Medium) 👑
825. Friends Of Appropriate Ages¶
2401. Longest Nice Subarray¶
1156. Swap For Longest Repeated Character Substring¶
424. Longest Repeating Character Replacement¶
from collections import defaultdict
# Sliding Window - Variable
def characterReplacement(s: str, k: int) -> int:
left = 0
maxCount = 0
counts = defaultdict(int)
maxLen = 0
for right in range(len(s)):
counts[s[right]] += 1
maxCount = max(maxCount, counts[s[right]])
while right - left + 1 - maxCount > k:
counts[s[left]] -= 1
left += 1
maxLen = max(maxLen, right - left + 1)
return maxLen
s = "ABAB"
k = 2
print(characterReplacement(s, k)) # 4
438. Find All Anagrams in a String¶
from typing import List
# Sliding Window Fixed Size
def findAnagrams(s: str, p: str) -> List[int]:
n, k = len(s), len(p)
target = [0 for _ in range(26)]
for ch in p:
target[ord(ch) - ord("a")] += 1
count = [0 for _ in range(26)]
left = 0
res = []
for right in range(n):
count[ord(s[right]) - ord("a")] += 1
if right < k - 1:
continue
if count == target:
res.append(left)
count[ord(s[left]) - ord("a")] -= 1
left += 1
return res
s = "cbaebabacd"
p = "abc"
print(findAnagrams(s, p)) # [0, 6]