Sliding Window¶
Table of Contents¶
- 159. Longest Substring with At Most Two Distinct Characters (Medium) 👑
- 340. Longest Substring with At Most K Distinct Characters (Medium) 👑
- 487. Max Consecutive Ones II (Medium) 👑
- 1100. Find K-Length Substrings With No Repeated Characters (Medium) 👑
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
487. Max Consecutive Ones II 👑¶
from typing import List
class Solution:
def findMaxConsecutiveOnes(self, nums: List[int]) -> int:
"""Sliding Window: O(n) time, O(1) space.
Maintain a window with at most one 0; shrink from left when a second 0 enters.
"""
left, zero, res = 0, 0, 0
for right in range(len(nums)):
if nums[right] == 0:
zero += 1
while zero > 1:
if nums[left] == 0:
zero -= 1
left += 1
res = max(res, right - left + 1)
return res
def test_find_max_consecutive_ones():
s = Solution()
for fn in (s.findMaxConsecutiveOnes,):
assert fn([1, 0, 1, 1, 0]) == 4
assert fn([1, 0, 1, 1, 0, 1]) == 4
assert fn([1, 1, 1, 1]) == 4
assert fn([0]) == 1
assert fn([0, 0]) == 1
1100. Find K-Length Substrings With No Repeated Characters 👑¶
from collections import defaultdict
# Sliding Window Fixed Size
def numKLenSubstrNoRepeats(s: str, k: int) -> int:
n = len(s)
if k > n:
return 0
counts = defaultdict(int)
res = 0
for i, ch in enumerate(s):
# add to the window
counts[ch] += 1
# form a valid window
if i < k - 1:
continue
# update
res += 1 if len(counts) == k else 0
# remove from the window
first = i - k + 1
counts[s[first]] -= 1
if counts[s[first]] == 0:
del counts[s[first]]
return res
if __name__ == "__main__":
s = "havefunonleetcode"
k = 5
assert numKLenSubstrNoRepeats(s, k) == 6