Geçen ay bir arkadaşım mülakata hazırlanırken aradı beni. “Şu sliding window soruları var ya,” dedi, “mantığını anlıyorum da pencere ne zaman küçülecek, ne zaman büyüyecek — kafam karışıyor.” Tam da LeetCode 424 üzerinde takılmıştı, yani Longest Repeating Character Replacement. Hani o sorulardan biri ki, ilk baktığında “aa kolay bu” diyorsun. Oturup yazmaya başlayınca ince noktalar birer birer çıkıyor ortaya — sanki soru seni test ediyor gibi (en azından benim deneyimim böyle). Ben de 2022’de Amazon mülakatına hazırlanırken bu soruyla epey cebelleşmiştim, o yüzden konuyu az çok iyi biliyorum. Gelin birlikte hem problemi çözelim hem de sliding window mantığını gerçekten kafamıza kazıyalım.
Problem Ne Diyor Tam Olarak?
Bakın şimdi. LeetCode 424 size bir string ve bir k sayısı veriyor (en azından benim deneyimim böyle). Diyor ki: “Bu string içinde en fazla k tane karakteri değiştirerek, tamamı aynı harften oluşan en uzun alt diziyi bul.” Mesela string “AABABBA” ve k=1 ise cevap 4. Çünkü bir tane B’yi A’ya çevirirseniz “AAAA” elde ediyorsunuz — ya da farklı bir pencerede farklı bir kombinasyon deneyebilirsiniz tabii.
Peki neden?
Dürüst olmak gerekirse, İlk bakışta brute force aklına geliyor. Her olası alt diziyi dene, her birinde en sık karakteri bul, geri kalanların sayısı k’dan küçükse kaydet… Ama bu O(n²) hatta O(n³) gibi bir karmaşıklığa gider. Mülakatçı sizi güzel güzel dinler, sonra “daha iyi yapabilir miyiz?” diye sorar. İşte tam o anda sliding window devreye giriyor.
Bu problem “medium” etiketli. Ama bence sınırda — neredeyse hard sayılabilir. Pencere küçültme mantığı, yani left bir düşüneyim… pointer’ı ne zaman ilerleteceksiniz, insanların en çok takıldığı nokta tam olarak burası. İtiraf edeyim: ben ilk çözdüğümde max_freq değişkenini neden küçültmediğimizi bir türlü anlayamamıştım. Birazdan ona da geleceğiz.
Sliding Window Mantığını Adım Adım Kuralım
Sliding window dediğimiz şey özünde şu: iki pointer var, left ve right. Right sürekli ilerliyor, pencereyi büyütüyor. Pencere geçersiz hale geldiğinde left’i ilerletip küçültüyorsunuz. Ama “geçersiz” ne demek burada? İşin can alıcı noktası tam da bu (ben de ilk duyduğumda şaşırmıştım)
Penceredeki toplam karakter sayısından, en sık tekrar eden karakterin sayısını çıkardığınızda — yani değiştirmeniz gereken karakter sayısını bulduğunuzda — bu sayı k’dan büyükse pencere geçersiz. Formüle dökersek:
Pencere boyutu — En sık karakter sayısı > k → Pencere geçersiz, left’i ilerlet.
Dur bir saniye, bunu somut bir örnekle açıklayayım. Diyelim pencerenizde “AABB” var ve k=1. Pencere boyutu 4, en sık karakter A veya B (ikisi de 2 kere). 4 — 2 = 2, ama k=1. Yani 2 > 1 — pencere geçersiz. Left’i bir ilerletmek lazım.
Peki pencerede “AAB” olsaydı? Boyut 3, en sık A (2 kere). üç — 2 = 1, k=1. 1 > 1 değil, yani pencere geçerli (ben de ilk duyduğumda şaşırmıştım). Güzel. Bu “AAB” dizisinde tek bir B’yi A’ya çevirirseniz “AAA” olur — 3 uzunluğunda tekrar eden karakter dizisi elde edersiniz.
Bakın, burayı atlarsanız yazının kalanı anlamsız kalır.
Neden max_freq Hiç Azaltılmıyor?
Bunu yaşayan biri olarak söyleyeyim, İşte bu kısım beni 2022’de bayağı düşündürmüştü. Ciddi ciddi. Kodda max_freq değişkeni ya artıyor ya da aynı kalıyor, asla azalmıyor. Left pointer’ı ilerlettiğinizde o karakterin frekansını düşürüyorsunuz ama max_freq’e dokunmuyorsunuz. Bu bir bug mu?
İlginç olan şu ki, Hayır.
Mantık şu: biz en uzun geçerli pencereyi arıyoruz. max_freq’i düşürmek bize daha kısa bir pencere verir — ki bu bizi zaten ilgilendirmiyor, çünkü daha önce o uzunlukta geçerli bir pencere zaten bulmuştuk. Yani max_freq bir nevi “şu ana kadar gördüğüm en iyi durum” kaydını tutuyor (evet, doğru duydunuz). Bu iyileştirme sayesinde pencere çok nadir gerçek anlamda küçülmüyor, sadece kayıyor (slide ediyor). Neden önemli bu? Zarif bir trick bu, hem de mülakatçıların açıklayabilmenizi beklediği türden.
Hmm, nasıl desem… Aslında şöyle de açıklayabiliriz: pencere boyutumuz ya büyüyor ya da aynı kalıyor. Asla küçülmüyor. Çünkü biz zaten en büyük geçerli pencereyi arıyoruz — daha küçüğünü bulmak bize hiçbir şey kazandırmaz. PQPM: Farklı Diller İçin Tek Bir Süreç Yöneticisi yazımızda bu konuya da değinmiştik.
Python Kodunu Satır Satır İnceleyelim
Şimdi gelelim kodun kendisine. Aşağıda her satırı açıklamalı olarak veriyorum:
class Solution:
def characterReplacement(self, s: str, k: int) -> int:
left, right = 0, 0 # İki pointer, ikisi de başlangıçta 0
max_length = 0 # Sonuç: en uzun geçerli pencere
char_freq = {} # Penceredeki her karakterin frekansı
max_freq = 0 # Penceredeki en sık karakterin frekansı
while right < len(s):
# Sağ pointer'daki karakteri frekans tablosuna ekle
char_freq[s[right]] = char_freq.get(s[right], 0) + 1
# max_freq'i güncelle (sadece artabilir!)
max_freq = max(max_freq, char_freq[s[right]])
# Pencere geçersizse → left'i ilerlet
if (right — left + 1) — max_freq > k:
char_freq[s[left]] -= 1
left += 1
# Sonucu güncelle
max_length = max(max_length, right — left + 1)
right += 1
return max_lengthDikkat ettiyseniz bir while döngüsü var, her adımda right bir ilerliyor. Left ise sadece — kendi adıma konuşayım — pencere geçersiz olduğunda ilerliyor — her adımda en fazla 1 adım. Bu da bize O(n) zaman karmaşıklığı veriyor. Alan karmaşıklığı? Sadece büyük harfler var (26 harf), yani char_freq dictionary’si en fazla 26 eleman tutuyor. O(1) diyebiliriz rahatlıkla.
Adım Adım Görsel İzleme: “AABABBA”, k=1
Kuru kodla anlamak zor. Gelin bir örnek üzerinde yürüyelim — ben bunu 2022’de kağıt üzerinde yaparak öğrenmiştim ve hâlâ en iyi yöntem bu bence.
| Adım | Left | Right | Pencere | char_freq | max_freq | Geçerli mi? | max_length |
|---|---|---|---|---|---|---|---|
| 1 | 0 | 0 | A | {A:1} | 1 | ✅ (1-1=0≤1) | 1 |
| 2 | 0 | 1 | AA | {A:2} | 2 | ✅ (2-2=0≤1) | 2 |
| 3 | 0 | 2 | AAB | {A:2,B:1} | 2 | ✅ (3-2=1≤1) | 3 |
| 4 | 0 | 3 | AABA | {A:3,B:1} | 3 | ✅ (4-3=1≤1) | 4 |
| 5 | 0 | 4 | AABAB | {A:3,B:2} | 3 | ❌ (5-3=2>1) | 4 |
| → | 1 | 4 | ABAB | {A:2,B:2} | 3 | left ilerle | 4 |
| 6 | 1 | 5 | ABABB | {A:2,B:3} | 3 | ❌ (5-3=2>1) | 4 |
| → | 2 | 5 | BABB | {A:1,B:3} | 3 | left ilerle | 4 |
| 7 | 2 | 6 | BABBA | {A:2,B:3} | 3 | ❌ (5-3=2>1) | 4 |
| → | 3 | 6 | ABBA | {A:2,B:2} | 3 | left ilerle | 4 |
Sonuç: 4. Pencere “AABA” (index 0-3) bize en uzun geçerli pencereyi verdi — tek bir B’yi A’ya çevirince “AAAA” oluyor. Bitti.
Tabloyu incelediğinizde bir şey hemen dikkat çekiyor olmalı. 5. adımda max_freq 3 oluyor ve bir daha hiç azalmıyor — char_freq azalsa bile. İşte yukarıda anlattığım optimize etmeun pratikte nasıl çalıştığını burada görüyorsunuz. Güzel değil mi? Gemini’nin Yeni Defter Hamlesi: Notlar Karışmasın yazımızda bu konuya da değinmiştik.
Sık Yapılan Hatalar ve Dikkat Edilmesi Gerekenler
1. max_freq’i Düşürmeye Çalışmak
En yaygın hata bu. Left ilerlerken “max_freq’i de güncelliyeyim” diye düşünüyorsunuz. Teknik olarak güncellemeniz gerekmiyor — üstelik güncellemeye kalkışırsanız, tüm frekans tablosunu tarayıp yeni max’ı bulmak isterseniz, her adımda O(26) ekstra iş yaparsınız. Yani toplam O(26n). Hâlâ lineer, evet, ama gereksiz yere yavaşlatıyorsunuz kodu.
2. if Yerine while Kullanmak
Bazı çözümlerde “while (right — left + 1) — max_freq > k” görürsünüz. Bu da çalışır, yanlış değil. Ama buradaki kodda if yeterli — neden? Çünkü her adımda right sadece 1 ilerliyor, dolayısıyla pencere en fazla 1 birim geçersizleşebilir (yanlış duymadınız). Bir if ile left’i bir kez ilerletmek yeterli (en azından benim deneyimim böyle). While kullanmak mantıksal olarak bozuk değil ama fazladan, gereksiz.
3. Boş String Edge Case’i
s boşsa ne olacak? Döngüye hiç girmeyecek, max_length 0 kalacak (buna dikkat edin). Doğru. Ama mülakatçıya bunu söylemeniz güzel bir artı puan — küçük bir detay, büyük fark yaratıyor.
Bu Pattern Başka Nerelerde Karşınıza Çıkar?
LeetCode 424’ün güzelliği şu: öğrendiğiniz pattern bir sürü başka soruda işe yarıyor. LeetCode 3 (Longest Substring Without Repeating Characters) benzer bir sliding window mantığı kullanıyor mesela. LeetCode 76 (Minimum Window Substring) biraz daha zor ama yine aynı iki pointer yaklaşımı (evet, doğru duydunuz). LeetCode 1004 (Max Consecutive Ones III) ise neredeyse aynı problem — sadece 0 ve 1’ler var, k tane 0’ı 1’e çeviriyorsunuz. Neredeyse kopya gibi aslında.
Geçen yıl bir junior arkadaşım bu dört soruyu art arda çözdükten sonra “sliding window artık refleks oldu” demişti. Bence de öyle. Bir kere pattern’i içselleştirince — ki bu tartışılır — varyasyonları görmek çok kolaylaşıyor — sanki aynı melodiyi farklı enstrümanlarla duyuyorsunuz. Bir de Java’da Method Overloading: Aynı İsim, Farklı İş yazımızda da bahsettiğimiz gibi, programlamadaki pek çok kavram aslında aynı temel fikrin farklı kılıklarda karşınıza çıkması. Daha fazla bilgi için Ajanlar Artık İş Yapıyor: API Kullanan Görev Motoru yazımıza bakabilirsiniz.
E tabi, algoritma çalışırken görselleştirme araçları da faydalı oluyor. Ben genelde kağıt-kalem kullanırım — eski kafalıyım bu konuda. Ama TraceLit gibi araçlar pointer’ların her adımda nerede olduğunu görmenizi sağlıyor, özellikle ilk öğrenirken işe yarıyor.
Kurumsal Mülakata Hazırlık Perspektifi
Küçük bir startup mülakatında muhtemelen bu soruyu doğrudan sormazlar. Ama FAANG seviyesi şirketlerde — Google, Amazon, Meta — sliding window soruları çok popüler. 2023’te bir tanıdığım Amazon SDE-2 mülakatında tam bu soruyu aldığını söylemişti. Mesele sadece doğru kodu yazmak değil; düşünce sürecinizi yüksek sesle, net biçimde anlatmak.
Açık konuşayım: mülakatçı sizden kodu ezberden yazmanızı beklemiyor. “Neden bu yaklaşımı seçtiniz?”, “Time complexity neden O(n)?”, “max_freq’i azaltmasak bile doğru sonucu nasıl alıyoruz?” — bu tür sorulara hazırlıklı olun. Ha bu arada, React Hooks’u Anlamak: Kuralların Arkasındaki Gerçek yazımızda da benzer bir şey söylemiştik — kuralı bilmek yetmez, arkasındaki “neden”i anlamak gerekir.
Aslında, Son bir şey söyleyeyim ve bitireyim: bu soruyu ilk seferde optimal çözemezseniz panik yapmayın. Ben de çözememistim. Önce brute force yazın, sonra optimize edin. Mülakatçılar zaten bu gelişim sürecini görmek istiyor — sihirli cevabı nereden bulduğunuzu değil, nasıl düşündüğünüzü.
Sıkça Sorulan Sorular
LeetCode 424’te max_freq neden azaltılmıyor?
Çünkü biz en uzun geçerli pencereyi arıyoruz. max_freq’i azaltmak sadece daha küçük pencereler üretir ki bunlar zaten mevcut en iyi sonucu geçemez. Bu bir optimizasyon — doğruluğu bozmadan gereksiz hesaplamayı atlıyor.
Bu problemin zaman ve alan karmaşıklığı nedir?
Eh, Zaman karmaşıklığı O(n) çünkü her pointer en fazla n kere ilerliyor. Alan karmaşıklığı O(1) çünkü frekans tablosu en fazla 26 eleman (büyük İngilizce harfler) tutuyor — bu sabit bir üst sınır.
Sliding window yerine başka bir yaklaşım kullanılabilir mi?
Şunu fark ettim: Binary search + frequency count yaklaşımı da var, O(n log n) karmaşıklığında. Ama sliding window hem daha hızlı hem de kodu daha temiz. Mülakatçı genelde sliding window çözümünü bekliyor.
Bu problem hangi diğer LeetCode sorularına benziyor?
Burada, dürüst olmak gerekirse, LeetCode 3, LeetCode 76, LeetCode 340 ve özellikle LeetCode 1004 (Max Consecutive Ones III) çok benzer pattern kullanıyor. 1004’ü çözerseniz 424’ün neredeyse aynısı olduğunu fark edersiniz.
Kodda if yerine while kullanmak sonucu değiştirir mi?
Hayır, ikisi de doğru çalışır. Ama bu implementasyonda if yeterli çünkü right her adımda sadece 1 ilerliyor. While kullanmak gereksiz ekstra kontrol demek — yanlış değil ama gereksiz.
Kaynaklar ve İleri Okuma
Neyse, i̇lginç olan şu ki, LeetCode 424 — Longest Repeating Character Replacement (Problem Sayfası)
LeetCode 424 Resmi Editorial ve Çözüm Açıklaması
Wikipedia — Sliding Window Tekniği
20+ yıl deneyimli Azure Solutions Architect. Microsoft sertifikalı bulut mimari ve DevOps danışmanı. Azure, yapay zekâ ve bulut teknolojileri üzerine Türkçe teknik içerikler üretiyor.
İlgili Yazılar
Bu içerik işinize yaradı mı?
Benzer içerikleri kaçırmamak için beni sosyal medyada takip edin.
