Longest Repeating Character Replacement Medium 0 attempts
LeetCode ↗

Longest Repeating Character Replacement

Medium Two Pointer LeetCode

You're given a string s made of uppercase English letters and a budget of k character replacements — each replacement lets you pick any character in the string and replace it with a different uppercase letter. Using at most k such replacements, find the longest substring you can create that consists of a single repeated letter.

Input Format
Implement characterReplacement(s, k). Inputs below show JavaScript function arguments; there is no stdin parsing.
Output Format
Return the result described in the statement.

Sample Input and Output

Example 1 · Run Sample

Input
s = "ABAB"
k = 2
Output
4

Example 2

Input
s = "AABABBA"
k = 1
Output
4
Constraints
  • 1 <= s.length <= 10^5
  • s consists of uppercase English letters
  • 0 <= k <= s.length
Test Cases (2)
Case 1
Args: ["ABAB",2] Expected: 4
Case 2
Args: ["AABABBA",1] Expected: 4
Topics
Two Pointer

Use a sliding window approach. Maintain a count of characters in the current window. If the window size minus the largest character frequency seen so far exceeds k, shrink the window from the left.

javascript
function characterReplacement(s, k) {
  const count = {};
  let left = 0, maxFreq = 0, result = 0;

  for (let right = 0; right < s.length; right++) {
    count[s[right]] = (count[s[right]] || 0) + 1;
    maxFreq = Math.max(maxFreq, count[s[right]]);

    while ((right - left + 1) - maxFreq > k) {
      count[s[left]]--;
      left++;
    }

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

  return result;
}

Time: O(n) Space: O(1) — at most 26 character counts

Saved in this browser only. Private to you.

JavaScript