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.
There may exists other ways to achieve this answer too.
for{
expand the sliding window
check if the current window is valid
if valid update the max substring length
if(){
since we are dealing with Longest Repeating Character Replacement
maxFrequency of any character is the anchor around which we base our replacements.
To make the entire window uniform, we only need to replace characters that are not the most frequent character.
Valid Window:
If the current window is valid, we can continue expanding it because the replacements required are within the allowed limit k.
}else{
invalid window condition
The size of the current window is end - start + 1
the number of characters that need replacement is:
window size - maxFrequency
if the number of replacements needed (windowSize - maxFrequency) exceeds k, then window is invalid, we must shrink it.
}
}
On Invalid Window:
When you shrink the window by moving start forward, the character at s[start] is removed from the window.
To accurately track the frequency of characters in the current window, the charCount map needs to be updated to reflect this removal.
function characterReplacement(s, k) {
const charCount = {};
let start = 0;
let maxCount = 0;
let maxLength = 0;
for (let end = 0; end < s.length; end++) {
// Update character frequency
charCount[s[end]] = (charCount[s[end]] || 0) + 1;
// Update the count of the most frequent character in the window
maxCount = Math.max(maxCount, charCount[s[end]]);
// Check if the window is valid
let windowSize = end - start + 1;
if (windowSize - maxCount > k) {
charCount[s[start]]--;
start++; // Shrink the window
}
// Update the maximum length
maxLength = Math.max(maxLength, end - start + 1);
}
return maxLength;
}
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:
Example 2:
for{
if(){
If the current window is valid, we can continue expanding it because the replacements required are within the allowed limit k.
}else{
}
}
On Invalid Window:
function characterReplacement(s, k) { const charCount = {}; let start = 0; let maxCount = 0; let maxLength = 0; for (let end = 0; end < s.length; end++) { // Update character frequency charCount[s[end]] = (charCount[s[end]] || 0) + 1; // Update the count of the most frequent character in the window maxCount = Math.max(maxCount, charCount[s[end]]); // Check if the window is valid let windowSize = end - start + 1; if (windowSize - maxCount > k) { charCount[s[start]]--; start++; // Shrink the window } // Update the maximum length maxLength = Math.max(maxLength, end - start + 1); } return maxLength; }