You are given a string s and an integer k. You can choose any character of the string and change it to any other uppercase English character. You can perform this operation at most k times.
Return the length of the longest substring containing the same letter you can get after performing the above operations.
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.
Constraints:
1 <= s.length <= 105sconsists of only uppercase English letters.0 <= k <= s.length
What is longest repeating character?
The longest substring which contains the same letter.
By looking at the question, it is as similar to 'Sliding Window', but it's not obvious at this moment.
How to find the maximum frequency of the character in an array? Click here
If we want to replace the characters in a substring and make it into the longest repeating, then we definitely want to find the character with maximum frequency and then replace all the other characters by this one, hence in this way, we can minimize the number of replacement.
Hence, with such idea within mind, when we build a sliding window [start, end], we want this window to have this property: (the length of the window) - (the maximum frequency of the character in this window) > k. Then we can see that [start, end-1] can be fit into k replacement.
If we can find such a sliding window, then how to we move this window? We can simply shift the start to start+1, since in this way this window will no longer hold the property (the length of the window) - (the maximum frequency of the character in this window) > k, and then we can keep moving end to end+1 to see if we have a longer window.
class Solution {
public:
int characterReplacement(string s, int k) {
int N = s.length();
int maxLength = 0;
int windowStart = 0;
vector<int> charCount(26);
int maxCount = 0;
for (int windowEnd = 0; windowEnd < N; windowEnd++) {
charCount[s[windowEnd] - 'A']++;
maxCount = max(maxCount, charCount[s[windowEnd] - 'A']);
if ((windowEnd - windowStart + 1) - maxCount > k) {
charCount[s[windowStart] - 'A']--;
windowStart++;
}
maxLength = max(maxLength, windowEnd - windowStart + 1);
}
return maxLength;
}
};To learn more about sliding window, click here.
Instead of the charCount vector, we can go with the unordered_map to get the frequency of each letters. This will reduce the space.
In any sliding window, we need to have a condition to slide the window.
Other Sliding Window Problems:
Comments
Post a Comment