Sliding Window Variable¶
Table of Contents¶
- 3. Longest Substring Without Repeating Characters (Medium)
- 159. Longest Substring with At Most Two Distinct Characters (Medium) 👑
- 424. Longest Repeating Character Replacement (Medium)
- 1208. Get Equal Substrings Within Budget (Medium)
- 1004. Max Consecutive Ones III (Medium)
- 438. Find All Anagrams in a String (Medium)
- 992. Subarrays with K Different Integers (Hard)
- 2024. Maximize the Confusion of an Exam (Medium)
3. Longest Substring Without Repeating Characters¶
class Solution:
def lengthOfLongestSubstring(self, s: str) -> int:
"""Sliding Window: O(n) time, O(min(n, charset)) space.
Jump the left edge past each repeated character's previous index.
"""
left = 0
res = 0
seen = {}
for right, ch in enumerate(s):
if ch in seen and seen[ch] >= left:
left = seen[ch] + 1
seen[ch] = right
res = max(res, right - left + 1)
return res
def lengthOfLongestSubstringSet(self, s: str) -> int:
"""Sliding Window Set: O(n) time, O(min(n, charset)) space.
Shrink until the current character is unique in the window.
"""
left = 0
res = 0
window = set()
for right, ch in enumerate(s):
while ch in window:
window.remove(s[left])
left += 1
window.add(ch)
res = max(res, right - left + 1)
return res
def test_length_of_longest_substring():
s = Solution()
cases = [
("abcabcbb", 3),
("bbbbb", 1),
("pwwkew", 3),
("", 0),
(" ", 1),
("abba", 2),
("dvdf", 3),
]
for text, expected in cases:
assert s.lengthOfLongestSubstring(text) == expected
assert s.lengthOfLongestSubstringSet(text) == expected
#include <iostream>
#include <string>
#include <unordered_set>
using namespace std;
int lengthOfLongestSubstring(string s) {
int n = s.length();
int res = 0;
int left = 0;
unordered_set<char> window;
for (int right = 0; right < n; right++) {
char ch = s[right];
while (window.find(ch) != window.end()) {
window.erase(s[left]);
left++;
}
window.insert(ch);
res = max(res, right - left + 1);
}
return (int)res;
}
int main() {
string s = "abcabcbb";
cout << lengthOfLongestSubstring(s) << endl; // 3
s = "bbbbb";
cout << lengthOfLongestSubstring(s) << endl; // 1
s = "pwwkew";
cout << lengthOfLongestSubstring(s) << endl; // 3
return 0;
}
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
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
1208. Get Equal Substrings Within Budget¶
# Sliding Window - Variable
def equalSubstring(s: str, t: str, maxCost: int) -> int:
left = 0
maxLen = 0
currentCost = 0
for right in range(len(s)):
currentCost += abs(ord(s[right]) - ord(t[right]))
while currentCost > maxCost:
currentCost -= abs(ord(s[left]) - ord(t[left]))
left += 1
maxLen = max(maxLen, right - left + 1)
return maxLen
s = "abcd"
t = "bcdf"
maxCost = 3
print(equalSubstring(s, t, maxCost)) # 3
1004. Max Consecutive Ones III¶
from typing import List
# Sliding Window - Variable
def longestOnes(nums: List[int], k: int) -> int:
left = 0
maxLen = 0
zero_count = 0
for right in range(len(nums)):
if nums[right] == 0:
zero_count += 1
while zero_count > k:
if nums[left] == 0:
zero_count -= 1
left += 1
maxLen = max(maxLen, right - left + 1)
return maxLen
nums = [1, 1, 1, 0, 0, 0, 1, 1, 1, 1, 0]
k = 2
print(longestOnes(nums, k)) # 6
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") == []
992. Subarrays with K Different Integers¶
from typing import List
# Sliding Window - Variable
def subarraysWithKDistinct(nums: List[int], k: int) -> int:
def atMost(k: int) -> int:
count = 0
left = 0
freq = {}
for right in range(len(nums)):
if nums[right] not in freq:
freq[nums[right]] = 0
freq[nums[right]] += 1
while len(freq) > k:
freq[nums[left]] -= 1
if freq[nums[left]] == 0:
del freq[nums[left]]
left += 1
count += right - left + 1
return count
return atMost(k) - atMost(k - 1)
nums = [1, 2, 1, 2, 3]
k = 2
print(subarraysWithKDistinct(nums, k)) # 7
2024. Maximize the Confusion of an Exam¶
# Sliding Window - Variable
def maxConsecutiveAnswers1(answerKey: str, k: int) -> int:
def maxConsecutiveChar(s: str, k: int, char: str) -> int:
max_len = 0
left = 0
count = 0 # num of str != char
for right in range(len(s)):
if s[right] != char:
count += 1
while count > k:
if s[left] != char:
count -= 1
left += 1
max_len = max(max_len, right - left + 1)
return max_len
max_t = maxConsecutiveChar(answerKey, k, "T")
max_f = maxConsecutiveChar(answerKey, k, "F")
return max(max_t, max_f)
# Sliding Window - Variable
def maxConsecutiveAnswers2(answerKey: str, k: int) -> int:
def maxConsecutiveChar(s: str, k: int, char: str) -> int:
max_len = 0
left, right = 0, 0
while right < len(s):
if s[right] != char:
k -= 1
while k < 0:
if s[left] != char:
k += 1
left += 1
max_len = max(max_len, right - left + 1)
right += 1
return max_len
max_t = maxConsecutiveChar(answerKey, k, "T")
max_f = maxConsecutiveChar(answerKey, k, "F")
return max(max_t, max_f)
# |-----------------|---------|------------|
# | Approach | Time | Space |
# |-----------------|---------|------------|
# | Sliding Window | O(N) | O(1) |
# |-----------------|---------|------------|
answerKey = "TTFF"
k = 2
print(maxConsecutiveAnswers1(answerKey, k)) # 4
print(maxConsecutiveAnswers2(answerKey, k)) # 4