CP #9 : Longest Substring Without Repeating Characters Problemi

 Problem surada.

Cozum

Ilk akla gelen naive cozumle baslayalim. 

Verilen stringi itere ederiz. 

Simdiye kadar gorulen karakterleri tutmak icin bir cache olustururuz. 

cur_maks ve maks adinda iki degiskende mevcut tekrar etmeyen substring uzunlugunu ve global maks degerini tutariz.

Eger eldeki karakter cache'te var ise cur_maks ve cache'i resetleriz. Yok ise, cur_maks degerini artirir ve de global maks ile kiyaslayip guncelleriz. 

Mesela bu yontem "abcabcbb" icin calisir. Yani leetcode'da Run Code yaptigimda pass etmisti. Ama submit ettigimizde gorecegiz ki bazi case'ler icin calismiyor. 

Ornek olarak, "dvdf" icin 2 degerini elde ederiz. Cunku dv ile basladik guzel sonra tekrar d gelince reset attik. Ve d geldigi noktadan ilerlemeye devam ettik. Ama aslinda d'yi ilk gordugumuz yere geri donmemiz gerekiyordu. Cunku 0 noktasindan degil de 1 noktasindan baslarsak en uzun tekrarsiz sunstringi elde ederiz. 

Revizyon

Yukarida bahsettigimiz metodu biraz modifiye edebiliriz. Diyelim ki cache'te olan bir karakter ile karsilastik. Bu durumda, cache'i resetlemeden once, o karakteri ilk gordumuz yere geri gitmemiz gerekiyor. Peki karakteri ilk gordugumuz yerin index'i kac? Bunu bilebilmenin en maliyetsiz yolu onu da cache' tutmak diye dusunuyorum. Bu durumda ilk basta bir set olarak implemente ettgim cache'i, bir dictionary sekline ceviriyorum ve key'ler karakter ise value da o karakterin indexi olacak sekilde cache tutuyorum. Implementasyona gecelim.

def lengthOfLongestSubstring(self, s):

    maks = 0

    cur_maks = 0

    cache = {}

    i = 0

    while i<len(s):

        if s[i] in cache:

            # tam o karakterin ilk goruldugu yere degil de bir sagina gitmemiz gerekli

            # yoksa zaten ilerde tekrar karsilasiriz ve tekrar bu noktaya doneriz ve donguden

            # cikamayiz

            i = cache[s[i]] + 1 

            cache = {}

        

        cur_maks +=1

        maks = max(maks, cur_maks)

        # normal sekilde ilerliyorz

        i = i + 1

    return maks

Analiz

Biz ne yaptik? Oncelikle bir cursor pozisyon degeri tutuyoruz (i). Egere cache'te olan bir karakter ile karsilasirsak bu cursor'u o karakterin bir sagindaki karaktere geri goturuyoruz. Ve saymaya devam ediyoruz. Oysa ki o karakterden sonra gelen karakterleri zaten saymistik. Bu kismi tekrar optimize edip, geri gitmeyi onleyebilecegimizi anliyoruz. 

Oyle ki, i yerine left seklinde bir isim vererek amacimizi daha iyi ortaya koyabiliriz. max length substring'in baslama yerini tutacak bu degisken. Ve de initial olarak sifir olacak. Daha sonra egere cache'te olan bir karaktere rastlarsak, left degerini buna gore guncelleyecegiz ama verilen string uzerinde itere etmeye de devam edecegiz. Buna sliding window ya da two pointers approach da diyebiliriz. 

def lengthOfLongestSubstring(self, s):

    left = 0

    cache = {}

    maks = 0

    for i in range(len(s)):

        if s[i] in cache:

            # burada left degerini direk cache'teki deger +1 seklinde guncellersek

            # abba orneginde oldugu gibi taa en basa donmus oluruz. 

            # bunu onlemek icin egere mevcut left degerinden daha buyukse cache'teki deger

            # ancak o zaman guncelliyoruz. 

            # yani aslinda left yalnizca saga dogru ilerleyebilir, geriye gitmez.

            left = max(left, cache[s[i]] + 1)

    

        cache[s[i]] = i

        maks = max(maks, i - left + 1)

return maks

 

Bu hali ile leetcode'da cok daha iyi performans verdigini gorecegiz. Hem geriye donmeleri onlemis olduk, gercek bir one-pass cozum elde ettik hem de cache'i surekli temizlemekten vazgecmis olduk. 

Son hali ile gayet acik ki O(n) time complexity var ve de hafiza gereksinimi de en kotu senaryoda tum karakterler farkli ise karakter sayisi kadar cache'te eleman barindirdigimizdan O(n) olmaktadir.