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 Substring Without Repeating Characters

Problem (yeniden ifade)

Bir s dizgisi verildiğinde, tekrarlayan karakter içermeyen en uzun alt dizginin uzunluğunu döndür.

Sezgi

Cevap bitişik bir aralık → kayar pencere. Sağı genişlet; pencerede tekrar belirdiğinde solu önceki oluşumun ötesine kaydır.

Yaklaşımlar

Kayar pencere + son görülme indeksi

Tested only

Time O(n)Space O(min(n, Σ))

Fikir. Benzersiz karakterli [left,right] penceresini tut. Map: char→son indeks. Pencerede tekrar olursa left = max(left, lastIndex+1). Maksimum uzunluğu izle.

Yürüyüş. s=“abcabcbb”. Pencereler büyür “a”,“ab”,“abc”, sonra ikinci a solu ilk a’nın ötesine iter → “bca”, … en iyi=3.

Trade-off. Doğrusal zaman optimal. Bu problemde last-seen map, frekans map’inden daha basittir.

Solution

export function lengthOfLongestSubstring(s: string): number {
  const last = new Map<string, number>();
  let left = 0;
  let best = 0;
  for (let right = 0; right < s.length; right++) {
    const ch = s[right]!;
    if (last.has(ch) && last.get(ch)! >= left) {
      left = last.get(ch)! + 1;
    }
    last.set(ch, right);
    best = Math.max(best, right - left + 1);
  }
  return best;
}

export function lengthOfLongestSubstring(s: string): number {
  const last = new Map<string, number>();
  let left = 0;
  let best = 0;
  for (let right = 0; right < s.length; right++) {
    const ch = s[right]!;
    if (last.has(ch) && last.get(ch)! >= left) {
      left = last.get(ch)! + 1;
    }
    last.set(ch, right);
    best = Math.max(best, right - left + 1);
  }
  return best;
}

Tüm alt dizgileri kontrol et

Tested only

Time O(n²)Space O(min(n, Σ))

Fikir. Her başlangıç indeksi için, karakterler set ile benzersiz kaldıkça uzat.

Yürüyüş. Her i’den tekrara kadar genişlet; max uzunluğu izle.

Trade-off. Basit ama karesel. Yalnızca referans implementasyon olarak kullan.

Solution

export function lengthBrute(s: string): number {
  let best = 0;
  for (let i = 0; i < s.length; i++) {
    const seen = new Set<string>();
    for (let j = i; j < s.length; j++) {
      if (seen.has(s[j]!)) break;
      seen.add(s[j]!);
      best = Math.max(best, j - i + 1);
    }
  }
  return best;
}

export function lengthBrute(s: string): number {
  let best = 0;
  for (let i = 0; i < s.length; i++) {
    const seen = new Set<string>();
    for (let j = i; j < s.length; j++) {
      if (seen.has(s[j]!)) break;
      seen.add(s[j]!);
      best = Math.max(best, j - i + 1);
    }
  }
  return best;
}

Şablon bağlantısı

Sliding Window şablonunun max-pencere formu: pencere geçersizken (tekrar varken) daralt.

Yansıma

Hangi pattern bunu 90 saniye içinde ele verdi?
Standart şablondan ne değişti?
Pencere/işaretçi mantığındaki dikkatsiz bir off-by-one’ı hangi girdi bozar?