Sliding window tekniği nedir? Tekrarsız en uzun alt dizeyi bulun.

Sliding window, bir dizi veya string üzerinde ardışık bir aralığı (pencere) iki indeksle temsil edip, her adımda pencereyi baştan hesaplamak yerine bir uçtan ekleyip diğer uçtan çıkararak güncelleme tekniğidir. İç içe döngülü O(n²) çözümleri genelde O(n)'e indirir.

İki türü vardır:

• Sabit boyutlu: "k uzunluklu alt dizilerin maksimum toplamı"
• Değişken boyutlu: koşul bozulunca sol uç daraltılır.

Problem: tekrarlanan karakter içermeyen en uzun alt dize

"abcabcbb" -> "abc", cevap 3.

def length_of_longest_substring(s: str) -> int:
    last_seen = {}       # karakter -> son görüldüğü indeks
    left = 0
    best = 0
    for right, ch in enumerate(s):
        # karakter pencere içinde tekrar ettiyse sol ucu atlat
        if ch in last_seen and last_seen[ch] >= left:
            left = last_seen[ch] + 1
        last_seen[ch] = right
        best = max(best, right - left + 1)
    return best

• Zaman: O(n), her karakter bir kez işlenir.
• Bellek: O(min(n, alfabe)).

Sabit pencere örneği

def max_sum_k(nums, k):
    window = sum(nums[:k])
    best = window
    for i in range(k, len(nums)):
        window += nums[i] - nums[i - k]   # gireni ekle, çıkanı çıkar
        best = max(best, window)
    return best

İpucu kelimeler: "ardışık alt dizi/alt dize", "en uzun/en kısa", "en fazla k farklı eleman".