Demo önizleme: Bu çözümler otomatik test paketini geçiyor ama insan tarafından incelenmedi. Trade-off ve yazıları taslak olarak değerlendirin.

Mediumsliding-window

Longest Repeating Character Replacement

Problem (restated)

You may replace at most k characters in string s. Return the length of the longest substring that can be made all the same character.

Intuition

In a window, replacements needed = window length, count of the most frequent character. Keep that ≤ k.

Approaches

Sliding window + max frequency

Tested only

Time O(n)Space O(1)

Idea. Expand right, track char counts and maxFreq in window. While (right-left+1, maxFreq) > k, shrink left.

Walkthrough. s=“AABABBA”, k=1. Window can hold “AABA” (1 replace) length 4; “ABABB” shrinks; best stays 4.

Trade-offs. maxFreq need not decrease when shrinking for correctness of the answer (window never needs to shrink below historical max).

Solution

export function characterReplacement(s: string, k: number): number {
  const cnt = new Array<number>(26).fill(0);
  let left = 0, maxFreq = 0, best = 0;
  for (let right = 0; right < s.length; right++) {
    const i = s.charCodeAt(right)! - 65;
    cnt[i]!++;
    maxFreq = Math.max(maxFreq, cnt[i]!);
    while (right - left + 1 - maxFreq > k) {
      cnt[s.charCodeAt(left)! - 65]!--;
      left++;
    }
    best = Math.max(best, right - left + 1);
  }
  return best;
}

export function characterReplacement(s: string, k: number): number {
  const cnt = new Array<number>(26).fill(0);
  let left = 0, maxFreq = 0, best = 0;
  for (let right = 0; right < s.length; right++) {
    const i = s.charCodeAt(right)! - 65;
    cnt[i]!++;
    maxFreq = Math.max(maxFreq, cnt[i]!);
    while (right - left + 1 - maxFreq > k) {
      cnt[s.charCodeAt(left)! - 65]!--;
      left++;
    }
    best = Math.max(best, right - left + 1);
  }
  return best;
}

Reflection

Which cue made you pick this pattern in under 90 seconds?
What input would break a wrong window invariant?