Sliding Window Variable Others¶
Table of Contents¶
- 1438. Longest Continuous Subarray With Absolute Diff Less Than or Equal to Limit (Medium)
- 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) 👑
1438. Longest Continuous Subarray With Absolute Diff Less Than or Equal to Limit¶
-
Tags: Array, Queue, Sliding Window, Heap Priority Queue, Ordered Set, Monotonic Queue
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]