LeetCode Meditations: Longest Repeating Character Replacement

The description for this problem says:

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.

For example:

characterReplacement('ABAB', 2);
// -> 4
// Explanation: Replace the two 'A's with two 'B's or vice versa.


characterReplacement('AABABBA', 1);
// -> 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.

This one is, I think, very tough, even though it's labeled as medium difficulty.

Let's take a deep breath, and look at one solution:

function characterReplacement(s: string, k: number): number {
  let count = Array.from({ length : 26 }, () => 0);
  let left = 0;
  let right = 0;
  let maxLength = 0;

  while (right < s.length) {
    count[s[right].charCodeAt(0) - 'A'.charCodeAt(0)]++;
    while ((right - left + 1) - Math.max(...count) > k) {
      count[s[left].charCodeAt(0) - 'A'.charCodeAt(0)]--;
      left++;
    }

    maxLength = Math.max(right - left + 1, maxLength);
    right++;
  }

  return maxLength;
};

Note that s[right].charCodeAt(0) - 'A'.charCodeAt(0) calculates the index of the uppercase character in the count array.
So, if s[right] is 'A', s[right].charCodeAt(0) is 65, and the result of the calculation is 0, making it the first index.
If s[right] is 'B', its charCode is 66, subtracting it from the charCode of 'A' makes it the index 1, etc.

Also, see the Group Anagrams problem, which uses a similar technique.

What we start with is an array to represent the frequency of characters that occur in the substrings we'll look at. We initialize count with length 26 for each letter, each one initially having the value of 0.

Then, we'll use the sliding window technique to check for substrings, so we'll initialize left and right pointers starting from the very first character's index: 0.
We'll also need to keep maxLength to keep track of the substring with the maximum length.

Then, as we look through each substring, we'll increase the character's count in the count array.

One important—and, maybe the most confusing—part is here:

while ((right - left + 1) - Math.max(...count) > k) {
  count[s[left].charCodeAt(0) - 'A'.charCodeAt(0)]--;
  left++;
}

Now, right - left + 1 is the length of our current window.
Math.max(...count) will give us the maximum number of times a character occurs within our current window, that is, the number of the longest repeating letters.
Subtracting it from the length of our window will give us the number of potential replacements we can make.
Remember that we can replace a character at most k times within a window, so, if the number of our potential replacements surpasses k, then we need to slide our window; that is, update the left pointer, also decreasing the value at the left's index in the count array.

We'll also keep track of our maxLength as we increase our window's length, and return it at the end as the result.

Time and space complexity

The time complexity for this solution is $O(n)$ as we loop through each character in s. The amount of space we additionally require for the count array is constant, of length 26, so the space complexity will be $O(1)$ .

This solution is adapted from NeetCode, where he also mentions a slight optimization.

I think this was a challenging problem, so it's time for another deep breath. Next up is the last problem Minimum Window Substring in the Sliding Window chapter, until then, happy coding.