Leetcode, Longest Substring Without Repeating Characters Problemi Çözümü (Python)

Sorunun özeti

Verilen stringte harflerinde tekrar olmayan en uzun kısmın karakter sayısının döndürülmesi isteniyor.

Çözüm

Önce değişkenleri ve while döngüsünü tanımlıyorum. while döngüsü, döngüdeki eleman sayısı kadar dönecek gibi gözüküyor olsa da aslında çok daha fazla dönecek. Çünkü döngüde geçerli substringde tekrarlayan karakter farkedildiğinde substringin ikinci harfinden kontrol tekrar başlıyor.

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        temp=""
        longest=""
        start=0
        i=0
        while i<(len(s)):

Eğer harf temp değişkeninde yoksa, temp değişkenine ekleniyor ve yeni temp daha önce kaydedilmiş en uzun substringten(longest) uzun ise yeni longest, temp oluyor.

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        temp=""
        longest=""
        start=0
        i=0
        while i<(len(s)):
            if s[i] not in temp:
                temp+=s[i]
                if len(longest)<len(temp):
                    longest=temp

Else if ise aynı harften temp içinde varsa çalışıyor. temp değişkeni boş stringe dönüştürülüyor. Burada önemli bir nokta var. Aynı karakterden her bulunduğunda kod, döngüye son substringin ikinci harfine dönerek tekrar başlıyor. Örneğin stringimiz "abcabcd" olsun. "a", "b", "c" harfleri sırasıyla temp'e ekleniyor. Tabi bu noktada longest="abc" oluyor. Döngüde ikici a harfi geldiğinde önce start, 1 artırılıyor(0'dan 1 oluyor.). Ardından i ise start'a eşitleniyor. Kodda i=start-1 olmasının sebebi, if kontrollerinden sonra her döngüde i zaten bir artırılıyor. Bu yüzden start'ı 1 eksilterek i'ye eşitlememiz gerekiyor. Bu işlemler sayesinde bu sefer kontrol "abcabcd" stringinin 1. indeksinden tekrar başlıyor. Bunu yapmasaydık 2. a tespit edildiğinde döngü ondan sonraki harften devam ederdi ve bu sefer arada olabilecek tekrarsız substringler bulunamazdı.

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        temp=""
        longest=""
        start=0
        i=0
        while i<(len(s)):
            if s[i] not in temp:
                temp+=s[i]
                if len(longest)<len(temp):
                    longest=temp

            elif s[i] in temp:
                start+=1
                i=start-1
                temp=""
            i+=1

En son longest'ın karakter sayısı döndürülüyor ve boş string verilmesi durumuna karşı bir kontrol bulunuyor.

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        temp=""
        longest=""
        start=0
        i=0
        while i<(len(s)):
            if s[i] not in temp:
                temp+=s[i]
                if len(longest)<len(temp):
                    longest=temp

            elif s[i] in temp:
                start+=1
                i=start-1
                temp=""
            i+=1

        return len(longest) if temp!="" else 0