Leetcode 3 Longest Substring Without Repeating Characters

Soru

Given a string s, find the length of the longest substring without repeating characters.

Örnek 1

Input: s = "abcabcbb"
Output: 3
Explanation: The answer is "abc", with the length of 3.

Örnek 2

Input: s = "bbbbb"
Output: 1
Explanation: The answer is "b", with the length of 1.

Çözüm

• Bir string içinde tekrar eden karakter olmadan en uzun alt diziyi bulmanızı ister. Bu problemde, alt dizinin içinde aynı karakterin birden fazla kez bulunmaması gerekmektedir.
• Girdi: Bir string s.
• Çıktı: Tekrar eden karakter içermeyen en uzun alt dizinin uzunluğu.
• Bu problem için yaygın bir yaklaşım, kaydırmalı pencere (sliding window) veya iki işaretçi tekniği ile birlikte bir hash set veya hash map kullanmaktır. Bu yöntemle, bir işaretçi sabit kalırken diğer işaretçi string boyunca kaydırılarak en uzun tekrar eden karakter içermeyen alt dizi bulunur.
• Çalışma Mekanizması:
• Değişkenlerin İnitialize Edilmesi: char_set tekrar eden karakterleri kontrol etmek için kullanılır. left ve right işaretçileri sıfırdan başlar. max_length maksimum uzunluğu takip eder.
• Döngü İle İşlem: right işaretçisi string boyunca ilerler. Her adımda, char_set içinde mevcut karakter kontrol edilir.
• Tekrar Eden Karakter Kontrolü: Eğer right işaretçisinin gösterdiği karakter zaten char_set içindeyse, bu karakter char_setten çıkarılana kadar left işaretçisi artırılır.
• Maksimum Uzunluğun Güncellenmesi: Her adımda, mevcut maksimum uzunluk, mevcut uzunluk ile karşılaştırılır ve gerekiyorsa güncellenir.
• Sonuç Dönüşü: Tüm işlemler tamamlandığında, hesaplanan maksimum uzunluk döndürülür.

Code

class Solution:
    def lengthOfLongestSubstring(self, s):
        char_set = set()
        left = 0
        max_length = 0
        
        for right in range(len(s)):
            while s[right] in char_set:
                char_set.remove(s[left])
                left += 1
            char_set.add(s[right])
            max_length = max(max_length, right - left + 1)
        
        return max_length

      

Complexity

• Time complexity (Zaman Karmaşıklığı) : O(n), burada n string s’nin uzunluğudur. Her karakter en fazla iki kez işlem görür (eklenir ve çıkarılır).
• Space complexity (Alan Karmaşıklığı) : O(min(n, m)), burada m karakter setinin boyutudur. En kötü durumda, tüm benzersiz karakterler char_set içine alınabilir.