Longest Repeating Character Replacement

MediumString Hash Table Sliding Window

A row of floor tiles is described by the string s, where each uppercase letter names the colour of one tile. A decorator may repaint at most k tiles, giving each repainted tile any colour they like.

Return the length of the longest stretch of adjacent tiles that can be made all one colour using those repaints.

Example 1

Input: s = "RGRRB", k = 1
Output: 4

Explanation: Repaint the G to get RRRR across the first four tiles. Covering all five would need two repaints.

Example 2

Input: s = "PQQPQQQ", k = 2
Output: 7

Explanation: Repainting both P tiles turns the whole row into Q.

Example 3

Input: s = "ZYXW", k = 0
Output: 1

Explanation: With no repaints allowed, the longest single-colour stretch is one tile.

Constraints

The row has between 1 and 10^5 tiles.
Every character of s is an uppercase English letter.
k is between 0 and the length of s.

💡 Hint 1

A window can be turned into one repeated letter when windowLength - (count of its most frequent letter) <= k.

💡 Hint 2

Slide a window over s with 26 letter counters. Grow it on the right; when it needs more than k changes, shrink it from the left.

💡 Hint 3

You only care about windows longer than the best one so far, so the "most frequent count" never needs to be decreased when the window shrinks.

Try it yourself first ✎

Solutions stick better after a real attempt. Peek when you're ready.

Approach

Use a sliding window with a count of each letter inside it. A window is fixable when its length minus the count of its most frequent letter, the number of letters you would have to change, is at most k. Extend the window to the right one letter at a time, updating maxCount; if the window then needs more than k changes, drop its leftmost letter. maxCount is never lowered: the window only has to beat the best length found so far, and that requires a higher maxCount anyway. The window length at the end of each step is a candidate answer.

Time O(n)Space O(1) (26 counters)

function characterReplacement(s, k) {
  const count = new Array(26).fill(0);
  let left = 0;
  let maxCount = 0;
  let best = 0;
  for (let right = 0; right < s.length; right++) {
    const c = s.charCodeAt(right) - 65;
    count[c]++;
    maxCount = Math.max(maxCount, count[c]);
    while (right - left + 1 - maxCount > k) {
      count[s.charCodeAt(left) - 65]--;
      left++;
    }
    best = Math.max(best, right - left + 1);
  }
  return best;
}

class Solution {
    public int characterReplacement(String s, int k) {
        int[] count = new int[26];
        int left = 0, maxCount = 0, best = 0;
        for (int right = 0; right < s.length(); right++) {
            int c = s.charAt(right) - 'A';
            count[c]++;
            maxCount = Math.max(maxCount, count[c]);
            while (right - left + 1 - maxCount > k) {
                count[s.charAt(left) - 'A']--;
                left++;
            }
            best = Math.max(best, right - left + 1);
        }
        return best;
    }
}

/**
 * @param {string} s
 * @param {number} k
 * @return {number}
 */
function characterReplacement(s, k) {

}

Ctrl/⌘ + ' run · Ctrl/⌘ + Enter submit