You are given a string
s
and an integerk
. You can choose any character of the string and change it to any other uppercase English character. You can perform this operation at mostk
times.
Return the length of the longest substring containing the same letter you can get after performing the above operations.
Time spent: 1h 20m | Runtime: 87.80% | Memory: 80.26%
Given a window
[start, end]
, a countdict
of the characters, and the frequency of the most common character, how can we evaluate those same values for[start + 1, end]
?
We don't need to solve this problem since the size of the window never needs to decrease. We're constantly looking to expand the window and may encounter "invalid" windows in our search.
k
by changing k
consecutive letters to that target.m
instances of a given character in a substring of length k + m
, the entire substring can be turned into the given character.k + m
where m
is the frequency of the most
common letter in that substring. Also keep count along the way.start
and end
move) unless a
new character encountered allows the window to expand.Time spent: 8m | Runtime: 77.37% | Memory: 99.42%
import collections
class Solution:
def characterReplacement(self, s: str, k: int) -> int:
counts = collections.defaultdict(int)
start = 0
most_frequent = 0
longest_length = 0
for end in range(len(s)):
counts[s[end]] += 1
most_frequent = max(most_frequent, counts[s[end]])
# If window size is greater than allowed, contract it.
if end - start + 1 > most_frequent + k:
counts[s[start]] -= 1
start += 1
longest_length = max(longest_length, end - start + 1)
return longest_length