Given a string s that consists of only uppercase English letters, you can perform at most k operations on that string.
In one operation, you can choose any character of the string and change it to any other uppercase English character.
Find the length of the longest sub-string containing all repeating letters you can get after performing the above operations.
Note:
Both the string's length and k will not exceed 104.
Example 1:
Input: s = "ABAB", k = 2 Output: 4 Explanation: Replace the two 'A's with two 'B's or vice versa.
Example 2:
Input: s = "AABABBA", k = 1 Output: 4 Explanation: Replace the one 'A' in the middle with 'B' and form "AABBBBA". The substring "BBBB" has the longest repeating letters, which is 4.
The description was taken from https://leetcode.com/problems/longest-repeating-character-replacement/.
#O(N) Time, O(1) Space
class Solution:
def characterReplacement(self, s: str, k: int) -> int:
window = {}
left, right = 0, 0
longest, max_char = 0, 0
while right < len(s):
if s[right] in window:
window[s[right]] += 1
else:
window[s[right]] = 1
max_char = max(max_char, window[s[right]])
replace = right - left + 1 - max_char
while replace > k:
window[s[left]] -= 1
left += 1
replace -= 1
longest = max(longest, right - left + 1) right += 1 return longestThe question requires us to return the length of a specific substring that satisfies a certain constraint.
When we see that requirement, we know that a sliding window may be a good approach.
What we can do is have two pointers that signify the left-bound and right-bound of our sliding window. We will use a hashmap to track the distinct characters along with their count and if we have more characters that we need to replace, we know that we need to shrink the left side of the sliding window.
That is the general template for sliding window problems, we will expand the right side until our window is no longer valid in which case we will shrink the left. In this case, the window will no longer be valid if we have more unique characters than replacements.
However, there is also a greedy component to the trick of this problem that will be covered later.
Let's start by initializing our window dictionary, this will let us group each unique character by their frequency.
window = {}
Next, we will create two running maximum variables, longest and max_char.
The first will let us know the longest valid substring so far and the other will let us know the character with the greatest frequency within the window.
longest, max_char = 0, 0
Now let's begin traversing the string.
We will continue until the right pointer has gone past the end of the string.
while right < len(s):
Just like other sliding window problems, our right pointer will be in charge of throwing values into the window. The left will be in charge of evicting values from it.
Let's throw the right character into the window and see if it is the character with the greatest frequency so far. If it is, we will update the maximum character to count to this character's frequency within the window.
while right < len(s):
if s[right] in window:
window[s[right]] += 1
else:
window[s[right]] = 1
max_char = max(max_char, window[s[right]])
After we know what the current maximum character is, we will calculate how many characters we need to replace within the current window.
This is the greedy trick of the problem.
Greedy problems entail prioritizing either the least or most costly tasks so that we may conserve the most resources. Here, the most costly task is the character with the greatest frequency within the window because it would cost the most replacements to change that character into all of the other ones.
To conserve the most resources, we will instead count how many characters we would need to change into this maximum frequency character by calculating the length of the window and subtracting the count of the maximum character.
AAABCA
replace = right - left + 1 - max_char
Once we have found how many characters we need to replace, we will see if this amount is within the replacement budget, k, that we were given.
If not, we will need to shrink the window on the left side until we are within budget.
while replace > k:
We will shrink the window by decrementing the frequency of the left character in the window and moving the left pointer to the right.
Each time we do this, we will decrement the replace value as well since we now need to replace one less character.
window[s[left]] -= 1
left += 1
replace -= 1
Once our window satisfies the given constraint, meaning we are within our replacement budget, we will see if this is the longest window we have so far.
longest = max(longest, right - left + 1)
After we have done that, we will continue expanding it by incrementing our right pointer.
right += 1
After we have traversed the entire string, we will return the longest window we found that was in the replacement budget.
return longest