Tekrarsız en uzun alt string

Problem

Bir string veriliyor. İçinde hiçbir karakterin iki kez geçmediği, bitişik en uzun parçanın (alt string) uzunluğunu döndür. Karakterler harf, rakam, sembol ve boşluk olabilir. Bitişik olmayan seçimler (alt dizi) sayılmaz.

Girdi:  "kodkodlama"
Çıktı:  6          ("kodlam")

Girdi:  "abba"
Çıktı:  2          ("ab" ya da "ba")

Netleştirme soruları

• Karakter kümesi ne? ASCII mi, Unicode mu? (Sayaç dizisi mi map mi kullanacağımı belirler.)
• Büyük-küçük harf farklı karakter mi?
• Boş string gelebilir mi? (Cevap 0.)
• Sadece uzunluk mu, alt string'in kendisi de mi isteniyor?
• String ne kadar uzun? (5×10⁴; O(n²) sınırda, O(n³) değil.)

İpuçları

Yaklaşım

Brute force: Her başlangıç noktasından sağa doğru, tekrar görene kadar bir set ile ilerle. O(n²) zaman (alfabe boyutu ile sınırlı: her başlangıçtan en fazla |Σ| adım), O(|Σ|) bellek. Tüm alt string'leri üretip her birini ayrıca kontrol etmek O(n³) olur.

Kayan pencere (set ile): [left, right] penceresini tekrarsız tut. Yeni karakter pencerede varsa, set'ten çıkararak left'i bir bir ilerlet. Her karakter en fazla bir kez girer, bir kez çıkar: O(n).

Optimal, son görülme index'i ile zıplama: Set yerine karakter → son index map'i tutarsan left'i tek tek ilerletmene gerek kalmaz: tekrar görülen karakterin önceki index'i prev ise left = prev + 1. İki yaklaşım da O(n); bu versiyon sabit çarpanı azaltır ve kodu kısaltır.

Kritik ayrıntı prev >= left kontrolü. "abba"'yı düşün: ikinci b'de left 2'ye zıplar. Sonra ikinci a gelir; map'te a'nın son index'i 0, ama bu artık pencerenin dışında. Kontrol olmadan left 1'e geri gider, pencere "bba" olur ve cevap yanlışlıkla 3 çıkar. Alternatif yazım: left = Math.max(left, prev + 1).

Java çözümü

import java.util.HashMap;
import java.util.Map;

public final class LongestSubstringWithoutRepeating {

    public int lengthOfLongestSubstring(String s) {
        Map<Character, Integer> lastIndex = new HashMap<>();       // karakter -> en son görüldüğü index
        int windowStart = 0;
        int longest = 0;
        for (int end = 0; end < s.length(); end++) {
            Integer previous = lastIndex.put(s.charAt(end), end);
            if (previous != null && previous >= windowStart) {
                windowStart = previous + 1;                        // tekrarın hemen sağına zıpla
            }
            longest = Math.max(longest, end - windowStart + 1);
        }
        return longest;
    }
}

Map.put bir önceki değeri döndürdüğü için "önceki index'i oku ve yenisini yaz" tek çağrıda yapılıyor. Karakter kümesi ASCII ile sınırlıysa map yerine int[128] (başlangıç değeri -1) kullanmak boxing'i ve hash maliyetini ortadan kaldırır; mülakatta bu optimizasyonu söylemek yeterli.

Karmaşıklık

• Zaman: O(n). right n kez ilerler; left sadece ileri gider; her adımda map işlemi ortalama O(1).
• Bellek: O(min(n, |Σ|)); map'te en fazla farklı karakter sayısı kadar giriş olur. ASCII dizisi ile O(1) (128 sabit).

Kenar durumlar ve testler

main içinde derlenip çalıştırıldı; 3.000 rastgele string'de (5 harfli alfabe, 0-19 uzunluk) her başlangıçtan set ile tarayan brute force ile karşılaştırıldı.

Mülakatçı için

Belki de en çok sorulan kayan pencere sorusu. Ayırt edici noktalar: adayın kayan pencere kalıbını adlandırıp adlandırmadığı, bayat index hatasını yapıp yapmadığı ve karakter kümesi varsayımını sorup sormadığı. int[128] kullanan bir aday ASCII varsayımını söylemiyorsa sor; Türkçe karakter içeren bir kullanıcı adında bu kod production'da ArrayIndexOutOfBoundsException atar.

İpucu zamanlaması: Aday O(n²)'de takılırsa "bir sonraki başlangıç noktasında, önceki taramadan elde ettiğin bilgiyi neden atıyorsun?" diye sor. Bayat index hatasını yaparsa "abba"'yı kodla birlikte yürütmesini iste. Set'li versiyonu yazarsa kabul et; zıplama versiyonunu takip olarak sorabilirsin.

Takip soruları:

1. En fazla k farklı karakter içeren en uzun alt string? (Beklenen: karakter → sayaç map'i, map boyutu k'yı aşınca soldan daralt; LeetCode 340.)
2. Alt string'in kendisini döndür; birden fazla en uzun varsa ilkini. (Beklenen: en iyi left ve uzunluğu tut, sadece kesin büyükse güncelle.)
3. Veri bir karakter stream'i ve her an "şu ana kadarki en uzun" isteniyor; bellek O(|Σ|) ile sınırlı. (Beklenen: aynı algoritma doğal olarak stream'de çalışır, sadece son index'ler ve global index gerekir.)

Benzer problemler

• Longest Substring with At Most K Distinct Characters (LeetCode 340).
• Longest Repeating Character Replacement (LeetCode 424).
• Minimum Window Substring (LeetCode 76): daralan pencere ile minimum (bu sette: minimum-window-substring).
• Permutation in String (LeetCode 567): sabit boyutlu pencere.