longest-repeating-character-replacement.ts

/**
 * 424. Longest Repeating Character Replacement  (Medium)
 * Link: https://leetcode.com/problems/longest-repeating-character-replacement/
 *
 * Given a string `s` of uppercase letters and an integer `k`, you may replace at
 * most k characters. Return the length of the longest substring containing a
 * single repeated letter achievable after those replacements.
 *
 * Example:
 *   Input:  s = "AABABBA", k = 1
 *   Output: 4            // replace one char to get "AABA" or "ABBB..." etc.
 *
 * Approach:
 *   Sliding window tracking letter counts and the count of the most frequent
 *   letter in the window (`maxFreq`). A window is valid when
 *   windowSize - maxFreq <= k (chars to replace). When it becomes invalid, slide
 *   the left edge. The answer is the largest window seen.
 *
 * Time:  O(n)
 * Space: O(1)  — at most 26 counts.
 */
export function characterReplacement(s: string, k: number): number {
  const counts = new Map<string, number>();
  let left = 0;
  let maxFreq = 0;
  let best = 0;

  for (let right = 0; right < s.length; right++) {
    const ch = s[right];
    counts.set(ch, (counts.get(ch) ?? 0) + 1);
    maxFreq = Math.max(maxFreq, counts.get(ch)!);

    while (right - left + 1 - maxFreq > k) {
      const leftCh = s[left];
      counts.set(leftCh, counts.get(leftCh)! - 1);
      left++;
    }

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

  return best;
}