Documenting LeetCode solving.
Q1
424. Longest Repeating Character Replacement
Medium. Sliding window
The condition to check if the current window is valid:
windowLength - maxFrequency <= k
class Solution:
def characterReplacement(self, s: str, k: int) -> int:
count = {}
res = 0
l = 0
for r in range(len(s)):
count[s[r]] = count.get(s[r], 0) + 1
while (r - l + 1) - max(count.values()) > k:
count[s[l]] -= 1
l += 1
res = max(res, r - l + 1)
return res
Optimize the way of getting maxFrequency:
We don't need to track the maxF when it's being decremented is because the result (max length) only increases when windowLength and maxF both increase.
class Solution:
def characterReplacement(self, s: str, k: int) -> int:
count = {}
res = 0
l = 0
# Track max frequency
maxF = 0
for r in range(len(s)):
count[s[r]] = count.get(s[r], 0) + 1
# maxF = maxF or the incremented count value
maxF = max(maxF, count[s[r]])
while (r - l + 1) - maxF > k:
count[s[l]] -= 1
l += 1
res = max(res, r - l + 1)
return res
Q2
Medium. Sliding window
From Neetcode, youtube.com/watch?v=UbyhOgBN834
class Solution:
def checkInclusion(self, s1: str, s2: str) -> bool:
if len(s1) > len(s2): return False
s1Count = [0] * 26
s2Count = [0] * 26
# initialize count map for s1 and s2 partially
for i in range(len(s1)):
s1Count[ord(s1[i]) - ord('a')] += 1
s2Count[ord(s2[i]) - ord('a')] += 1
# Count matches
matches = 0
for i in range(26):
matches += (1 if s1Count[i] == s2Count[i] else 0)
l = 0
for r in range(len(s1), len(s2)):
if matches == 26: return True
# Check if the new right character matches a one in s1
index = ord(s2[r]) - ord('a')
s2Count[index] += 1
if s2Count[index] == s1Count[index]:
matches += 1
elif s1Count[index] + 1 == s2Count[index]:
matches -= 1
# Check if removing the left character makes s1 and
# the window string matches
index = ord(s2[l]) - ord('a')
s2Count[index] -= 1
if s2Count[index] == s1Count[index]:
matches += 1
elif s1Count[index] - 1 == s2Count[index]:
matches -= 1
# Increment left pointer afterward
l += 1
return matches == 26