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 (yeniden ifade)

s dizgisinde en fazla k karakteri değiştirebilirsin. Tamamen aynı karaktere dönüştürülebilecek en uzun alt dizginin uzunluğunu döndür.

Sezgi

Bir pencerede gereken değişiklik = pencere uzunluğu − en sık karakterin sayısı. Bunu ≤ k tut.

Yaklaşımlar

Kayar pencere + maksimum frekans

Doğrulanmadı

Zaman O(n)Alan O(1)

Fikir. Sağı genişlet, penceredeki karakter sayılarını ve maxFreq’i izle. (right-left+1, maxFreq) > k iken solu daralt.

Yürüyüş. s=“AABABBA”, k=1. Pencere “AABA” tutabilir (1 değişiklik) uzunluk 4; “ABABB” daralır; en iyi 4 kalır.

Trade-off. Cevabın doğruluğu için daralırken maxFreq’in azalması gerekmez (pencere tarihsel max’ın altına inmek zorunda değildir).

Çözüm

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;
}

Şablon bağlantısı

Max-frekans sayaçlı sliding window: window − maxFreq > k iken küçült.

Yansıma

Pencere boyu − en sık karakter ≤ k değişmezi nedir? En sıkı dışarı atınca mı güncellersin?
k = 0 ve k = n uçları: cevap 1’lerin max koşusu ve n.
En sıkı her daralmada yeniden saymazsan (yalnızca artırırsan) neden hâlâ doğru?