不定长滑动窗口求大进阶 Variable Sliding Window Max Advanced¶
Table of Contents¶
- 2730. Find the Longest Semi-Repetitive Substring (Medium)
- 2779. Maximum Beauty of an Array After Applying Operation (Medium)
- 1838. Frequency of the Most Frequent Element (Medium)
- 2516. Take K of Each Character From Left and Right (Medium)
- 2831. Find the Longest Equal Subarray (Medium)
- 2271. Maximum White Tiles Covered by a Carpet (Medium)
- 2106. Maximum Fruits Harvested After at Most K Steps (Hard)
- 2555. Maximize Win From Two Segments (Medium)
- 2009. Minimum Number of Operations to Make Array Continuous (Hard)
- 1610. Maximum Number of Visible Points (Hard)
- 2781. Length of the Longest Valid Substring (Hard)
- 3411. Maximum Subarray With Equal Products (Easy)
- 2968. Apply Operations to Maximize Frequency Score (Hard)
- 1040. Moving Stones Until Consecutive II (Medium)
- 3413. Maximum Coins From K Consecutive Bags (Medium)
- 395. Longest Substring with At Least K Repeating Characters (Medium)
- 1763. Longest Nice Substring (Easy)
- 487. Max Consecutive Ones II (Medium) 👑
- 159. Longest Substring with At Most Two Distinct Characters (Medium) 👑
- 340. Longest Substring with At Most K Distinct Characters (Medium) 👑
2730. Find the Longest Semi-Repetitive Substring¶
# Sliding Window Variable Max
def longestSemiRepetitiveSubstring(s: str) -> int:
n = len(s)
left = 0
repeat = 0
res = 1
for right in range(1, n):
if s[right] == s[right - 1]:
repeat += 1
while repeat > 1:
if s[left] == s[left + 1]:
repeat -= 1
left += 1
res = max(res, right - left + 1)
return res
if __name__ == "__main__":
assert longestSemiRepetitiveSubstring("abacaba") == 7
assert longestSemiRepetitiveSubstring("aa") == 2
assert longestSemiRepetitiveSubstring("a") == 1
assert longestSemiRepetitiveSubstring("abcde") == 5
2779. Maximum Beauty of an Array After Applying Operation¶
from typing import List
# Sliding Window Variable Max
def maximumBeauty(nums: List[int], k: int) -> int:
nums.sort()
res, left = 0, 0
for right, x in enumerate(nums):
while x - nums[left] > k * 2:
left += 1
res = max(res, right - left + 1)
return res
if __name__ == "__main__":
assert maximumBeauty([4, 6, 1, 2], 2) == 3
1838. Frequency of the Most Frequent Element¶
2516. Take K of Each Character From Left and Right¶
2831. Find the Longest Equal Subarray¶
2271. Maximum White Tiles Covered by a Carpet¶
2106. Maximum Fruits Harvested After at Most K Steps¶
2555. Maximize Win From Two Segments¶
from typing import List
# Sliding Window - Variable
def maximizeWin(prizePositions: List[int], k: int) -> int:
n = len(prizePositions)
if 2 * k >= prizePositions[-1] - prizePositions[0]:
return n
ans = left = 0
mx = [0] * (n + 1)
for right, p in enumerate(prizePositions):
while p - prizePositions[left] > k:
left += 1
ans = max(ans, mx[left] + right - left + 1)
mx[right + 1] = max(mx[right], right - left + 1)
return ans
prizePositions = [1, 1, 2, 2, 3, 3, 5]
k = 2
print(maximizeWin(prizePositions, k)) # 7
2009. Minimum Number of Operations to Make Array Continuous¶
1610. Maximum Number of Visible Points¶
2781. Length of the Longest Valid Substring¶
3411. Maximum Subarray With Equal Products¶
2968. Apply Operations to Maximize Frequency Score¶
1040. Moving Stones Until Consecutive II¶
3413. Maximum Coins From K Consecutive Bags¶
395. Longest Substring with At Least K Repeating Characters¶
1763. Longest Nice Substring¶
487. Max Consecutive Ones II 👑¶
159. Longest Substring with At Most Two Distinct Characters 👑¶
"""
- Prerequisite: 3. Longest Substring Without Repeating Characters
"""
from collections import defaultdict
# Sliding Window - Variable
def lengthOfLongestSubstringTwoDistinct(s: str) -> int:
n = len(s)
if n <= 2:
return n
window = defaultdict(int)
left, res = 0, 0
for right in range(n):
window[s[right]] += 1
while len(window) > 2:
window[s[left]] -= 1
if window[s[left]] == 0:
del window[s[left]]
left += 1
res = max(res, right - left + 1)
return res
s = "ccaabbb"
assert lengthOfLongestSubstringTwoDistinct(s) == 5
340. Longest Substring with At Most K Distinct Characters 👑¶
from collections import defaultdict
# Sliding Window Variable
def lengthOfLongestSubstringKDistinct(s: str, k: int) -> int:
n = len(s)
if n <= k:
return n
window = defaultdict(int)
left, res = 0, 0
for right in range(n):
window[s[right]] += 1
while len(window) > k:
window[s[left]] -= 1
if window[s[left]] == 0:
del window[s[left]]
left += 1
res = max(res, right - left + 1)
return res
s = "eceba"
k = 2
assert lengthOfLongestSubstringKDistinct(s, k) == 3