Longest Repeating Character Replacement | Sliding Window | Leetcode

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{

1. expand the sliding window
2. check if the current window is valid
3. if valid update the max substring length

if(){

1. since we are dealing with Longest Repeating Character Replacement
2. maxFrequency of any character is the anchor around which we base our replacements.
3. 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{

1. invalid window condition
2. The size of the current window is end - start + 1
3. the number of characters that need replacement is:
4. window size - maxFrequency
5. 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;
}