不定长滑动窗口其他 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
class Solution:
def findAnagrams(self, s: str, p: str) -> List[int]:
"""Fixed Sliding Window: O(n + m) time, O(1) space.
Track 26 lowercase counts for the current window of length len(p).
"""
if len(p) > len(s):
return []
target = [0] * 26
window = [0] * 26
for i, ch in enumerate(p):
target[ord(ch) - ord("a")] += 1
window[ord(s[i]) - ord("a")] += 1
res = []
if window == target:
res.append(0)
left = 0
for right in range(len(p), len(s)):
window[ord(s[right]) - ord("a")] += 1
window[ord(s[left]) - ord("a")] -= 1
left += 1
if window == target:
res.append(left)
return res
def test_find_anagrams():
s = Solution()
assert s.findAnagrams("cbaebabacd", "abc") == [0, 6]
assert s.findAnagrams("abab", "ab") == [0, 1, 2]
assert s.findAnagrams("af", "be") == []
assert s.findAnagrams("baa", "aa") == [1]
assert s.findAnagrams("", "a") == []