Longest Repeating Character Replacement Medium 0 attempts
LeetCode ↗

Longest Repeating Character Replacement

Medium Two Pointer 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.

Sample Input
s = "ABAB", k = 2
Sample Output
4
Constraints
  • 1 <= s.length <= 10^5
  • s consists of uppercase English letters
  • 0 <= k <= s.length
Test Cases
Case 1
Args: ["ABAB",2] 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 most frequent character count exceeds k, shrink the window from the left.

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