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

Hardsliding-window

Minimum Window Substring

Problem (yeniden ifade)

s ve t stringleri verilir. t’nin her karakterini (en az aynı çokluklarla) kapsayan minimum uzunluklu s alt stringini döndür. Böyle pencere yoksa boş string. Aynı uzunlukta birkaç minimum varsa herhangi biri kabul.

Sezgi

Bu kayan pencerenin min-pencere şekli; “en uzun geçerli” şekli değil:

Pencere geçerli olana kadar ( t’yi kapsayana kadar) right’ı genişlet.
Geçerli kaldığı sürece left’i daralt ve en iyi (en kısa) pencereyi izle.
Daraltma geçerliliği bozunca yeniden genişlet.

Değişmez: “pencere t’den gereken tüm sayıları içerir.”

Yaklaşımlar

need/have sayaçlı kayan pencere

Tested only

Time O(|s| + |t|)Space O(Σ)

Fikir. t’den need frekansları ve bir missing (veya have/needTypes) sayacı kur. right’ı ilerlet; yararlıyken o karakterin need’ini azalt. missing == 0 iken pencere geçerli: s[left..right] kaydet, sonra geçersiz olana kadar left’i ilerlet ve need’i geri yükle.

Adım adım. s = "ADOBECODEBANC", t = "ABC".

adım	pencere (fikir)	notlar
ilk tam kapsama	`ADOBEC`	ilk geçerli, uzunluk 6
geçerliyken daralt	hâlâ tam kapsama gerekir	en iyiyi izle
sonra genişlet/daralt	`BANC`	daha iyi uzunluk 4 → cevap

Ödünleşimler. Her uç en fazla bir kez hareket ettiğinden hâlâ O(|s|). Zor kısım defter tutma: “need” ile “pencere sayacı”nı karıştırırsan az daraltırsın veya eksik kapsamayı kabul edersin. ASCII için sabit boyutlu dizi hash map’ten iyidir.

Solution

export function minWindow(s: string, t: string): string {
  if (!t) return "";
  const need = new Map<string, number>();
  for (const ch of t) need.set(ch, (need.get(ch) ?? 0) + 1);
  let missing = need.size;
  let left = 0;
  let bestL = 0, bestLen = Infinity;
  const window = new Map<string, number>();
  for (let right = 0; right < s.length; right++) {
    const ch = s[right]!;
    window.set(ch, (window.get(ch) ?? 0) + 1);
    if (need.has(ch) && window.get(ch) === need.get(ch)) missing--;
    while (missing === 0) {
      if (right - left + 1 < bestLen) {
        bestLen = right - left + 1;
        bestL = left;
      }
      const leftCh = s[left]!;
      window.set(leftCh, (window.get(leftCh) ?? 0) - 1);
      if (need.has(leftCh) && (window.get(leftCh) ?? 0) < need.get(leftCh)!) missing++;
      left++;
    }
  }
  return bestLen === Infinity ? "" : s.slice(bestL, bestL + bestLen);
}

export function minWindow(s: string, t: string): string {
  if (!t) return "";
  const need = new Map<string, number>();
  for (const ch of t) need.set(ch, (need.get(ch) ?? 0) + 1);
  let missing = need.size;
  let left = 0;
  let bestL = 0, bestLen = Infinity;
  const window = new Map<string, number>();
  for (let right = 0; right < s.length; right++) {
    const ch = s[right]!;
    window.set(ch, (window.get(ch) ?? 0) + 1);
    if (need.has(ch) && window.get(ch) === need.get(ch)) missing--;
    while (missing === 0) {
      if (right - left + 1 < bestLen) {
        bestLen = right - left + 1;
        bestL = left;
      }
      const leftCh = s[left]!;
      window.set(leftCh, (window.get(leftCh) ?? 0) - 1);
      if (need.has(leftCh) && (window.get(leftCh) ?? 0) < need.get(leftCh)!) missing++;
      left++;
    }
  }
  return bestLen === Infinity ? "" : s.slice(bestL, bestL + bestLen);
}

Şablon bağlantısı

Varsayılan max-pencere şablonunun tersi: orada geçersiz iken daraltırsın ve geçerliyken uzunluğu güncellersin. Burada geçerliyken daraltırsın ve ancak o zaman minimumu güncellersin. Her iki şekil için sliding-window şablon başlığına bak.

Sık hatalar

t’de tekrar varken sayım yerine varlık (set) izlemek.
Pencere tamamen geçerli olmadan cevabı güncellemek.
Daralttıktan sonra right - left + 1 uzunluğunda off-by-one.

Yansıma

Alışkanlıkla en-uzun-pencereye mi kaydın? “Minimum kapsama” ipucu nedir?
t’de tekrar varken yalnızca varlık (set) izlersen ne bozulur?
Boş t / kapsama yok: ne döndürmelisin?