Tüm karakterleri kapsayan en kısa pencere

Problem

İki string veriliyor: s (aranacak metin) ve t (istenen karakterler). s'nin, t'deki her karakteri en az t'de geçtiği sayıda içeren en kısa bitişik parçasını döndür. t'de bir karakter iki kez geçiyorsa pencerede de en az iki kez olmalı. Böyle bir parça yoksa boş string döndür. Karakterler büyük-küçük harf duyarlı İngilizce harflerdir; en kısa pencere tek olarak garanti edilir.

Girdi:  s = "XKTAYBKZTA", t = "KAT"
Çıktı:  "KTA"

Girdi:  s = "a", t = "aa"
Çıktı:  ""          (s'de yeterli sayıda 'a' yok)

Netleştirme soruları

• t'deki tekrarlar sayılıyor mu? ("AA" için pencerede iki A gerekli mi?)
• Büyük-küçük harf duyarlı mı?
• Karakter kümesi ne? (Sayaç dizisinin boyutu.)
• Birden fazla en kısa pencere varsa hangisi? (LeetCode'da tekil garanti; genelde ilki.)
• t boşsa ne dönmeli?
• Uzunluklar? (10⁵; O(n × m) bile riskli.)

İpuçları

Yaklaşım

Brute force: Tüm (i, j) alt string'lerini üret, her biri için t'yi kapsayıp kapsamadığını sayaçla kontrol et. O(n² × |Σ|) ya da O(n³). Biraz daha iyisi: her başlangıç için sağa doğru ilerleyip ilk geçerli noktada durmak, O(n²).

Optimal, genişle-daralt kayan pencere: İki aşamalı ritim:

1. Genişlet: right'ı ilerlet, karakteri pencereye ekle.
2. Daralt: Pencere geçerli olduğu sürece (missing == 0) en iyi sonucu güncelle ve left'i ilerlet.

Neden doğru? Her right için, o right'ta biten geçerli pencerelerin en kısası, daraltma döngüsünün durduğu noktadan bir önceki left ile verilir. left'i hiçbir zaman geri götürmemize gerek yoktur: daha büyük bir right için daha küçük bir left asla daha kısa pencere vermez.

Tek sayaç hilesi: need[c], pencerenin c karakterine olan borcunu tutar. Negatif değer "fazlası var" demektir (t'de olmayan karakterler de negatife düşer; zararsız). missing, t'nin toplam karakter sayısından başlar ve sadece borçlu bir karakter geldiğinde azalır. Böylece geçerlilik kontrolü O(1) olur. Alternatif yaygın yazım "formed / required" (farklı karakter bazında) aynı fikri farklı karakter sayısıyla yapar.

Java çözümü

public final class MinimumWindowSubstring {

    public String minWindow(String s, String t) {
        if (t.isEmpty() || s.length() < t.length()) {
            return "";
        }
        int[] need = new int[128];                                 // ASCII harfler varsayımı
        for (int i = 0; i < t.length(); i++) {
            need[t.charAt(i)]++;
        }
        int missing = t.length();                                  // pencerede hâlâ eksik olan karakter adedi
        int bestStart = 0, bestLength = Integer.MAX_VALUE;
        int left = 0;
        for (int right = 0; right < s.length(); right++) {
            if (need[s.charAt(right)]-- > 0) {
                missing--;                                         // ihtiyaç duyulan bir karakter geldi
            }
            while (missing == 0) {                                 // pencere geçerli: soldan daralt
                if (right - left + 1 < bestLength) {
                    bestStart = left;
                    bestLength = right - left + 1;
                }
                if (++need[s.charAt(left)] > 0) {
                    missing++;                                     // gerekli bir karakteri kaybettik
                }
                left++;
            }
        }
        return bestLength == Integer.MAX_VALUE ? "" : s.substring(bestStart, bestStart + bestLength);
    }
}

need[s.charAt(right)]-- > 0 ifadesinde sonek -- önemli: karşılaştırma eski değerle yapılır, sonra azaltılır. Daraltmada önek ++ ile yeni değer kontrol edilir. Bu ifadeleri okunurluk için iki satıra bölmek de tamamen kabul edilebilir; mülakatta kendi okuduğun gibi yaz.

Sonucu her adımda substring ile üretmek yerine başlangıç ve uzunluğu tutup sonda bir kez kesmek, gereksiz string kopyalarını önler.

Karmaşıklık

• Zaman: O(|s| + |t|). right |s| kez, left en fazla |s| kez ilerler; her adım O(1).
• Bellek: O(|Σ|) = O(128), yani sabit.

Kenar durumlar ve testler

main içinde derlenip çalıştırıldı; 3.000 rastgele girdide (4 harfli alfabe, s 0-13, t 1-4 uzunluk) tüm alt string'leri deneyen brute force ile karşılaştırıldı. Birden fazla en kısa pencere olabileceği için uzunluk, kapsama ve s içinde yer alma ayrı ayrı doğrulandı.

Mülakatçı için

Kayan pencerenin "Zor" seviyesi: adayın genişle-daralt ritmini kurabilmesi ve geçerlilik kontrolünü O(1)'e indirebilmesi beklenir. Pek çok aday her adımda iki sayaç dizisini karşılaştırır (O(52 × n)); bu da kabul edilebilir bir çözümdür, ama missing sayacını bulan aday daha güçlü sinyal verir. En sık hata t'deki tekrarları yok saymak (set kullanmak).

İpucu zamanlaması: Aday 10 dakika içinde pencere fikrine ulaşamazsa ilk ipucunu ver. Her adımda tüm sayaçları karşılaştırıyorsa kod bittikten sonra "bunu O(1)'de bilebilir misin?" diye sor; zorunlu değil. Daraltma döngüsünde missing++ koşulunu yanlış kurarsa "aa", "aa" örneğini yürütmesini iste.

Takip soruları:

1. t'deki karakterlerin pencerede aynı sırayla (alt dizi olarak) geçmesi gerekseydi? (Beklenen: Minimum Window Subsequence, LeetCode 727; iki işaretçiyle ileri-geri tarama ya da DP.)
2. s çok uzun ve t kısa; s'deki ilgisiz karakterleri atlayarak hızlandırabilir misin? (Beklenen: sadece t'deki karakterlerin index'lerinden oluşan filtrelenmiş liste üzerinde aynı pencere.)
3. Bu bir log arama özelliği: "Bu üç hata kodunun hepsini içeren en kısa zaman aralığı" isteniyor. (Beklenen: aynı algoritma; karakter yerine event tipi, uzunluk yerine zaman farkı; stream'de çalışabilir.)

Benzer problemler

• Longest Substring Without Repeating Characters (LeetCode 3) (bu sette: longest-substring-without-repeating-characters).
• Find All Anagrams in a String (LeetCode 438): sabit pencere ve aynı sayaç fikri.
• Permutation in String (LeetCode 567).
• Minimum Window Subsequence (LeetCode 727).
• Smallest Range Covering Elements from K Lists (LeetCode 632): çok listeli pencere + heap.