Longest Substring Without Repeating Characters

Q: Bir alt dize ile bir alt dizi arasındaki fark nedir?

Bir alt dize, coddycode içindeki ode gibi, yan yana duran karakterlerden oluşan bir bloktur. Bir alt dizi karakterleri atlayabilir; örneğin cdy . Bu problem bir alt dize istediği için iki ucu olan bir pencere işe yarar.

OrtaKayan pencere Hashing

+10

Bir s dizgeniz var. Yan yana duran karakterlerden oluşan ve hiçbir karakterin iki kez geçmediği en uzun alt dizgeyi bulun ve uzunluğunu döndürün.

Büyük ve küçük harfler farklı karakterler sayılır; bu nedenle a ve A tekrar değildir.

Fonksiyon

lengthOfLongestSubstring(s: string) → integer

sstring: aranacak dize
Döndürürinteger: Tekrarlanan karakter içermeyen en uzun alt dizenin uzunluğu

Kısıtlar

1 ≤ s.length ≤ 5 × 10⁴
s yalnızca İngilizce harfleri (küçük ve büyük) ve rakamları içerir.
Büyük ve küçük harfler farklı karakterlerdir.

Örnekler

Girdi: s = "coddycode"
Çıktı: 5
Açıklama: ycode beş farklı karakter içerir. Önüne d eklemek, iki kez d içeren dycode sonucunu verir ve beş veya daha fazla karakterlik başka hiçbir dizi tekrar içermez.

Girdi: s = "racecar"
Çıktı: 4
Açıklama: Hem race hem de ecar dört farklı harften oluşur. Beş harften oluşan her dizide aynı harf iki kez bulunur.

Girdi: s = "a1b2a3b"
Çıktı: 5
Açıklama: Rakamlar da karakter sayılır, bu yüzden 1b2a3 beş farklı karakter içerir. Altı karakterlik iki dizinin her ikisinde de ikinci bir a ya da ikinci bir b bulunur.

Ek soru

s harfler ve rakamlar yerine herhangi bir Unicode karakterini tutabilseydi neyi değiştirirdin?

Çözüm

Bir pencere tut: yinelenen karakter içermeyen bir dizinin etrafında iki sınır. Sağ sınır her karakteri bir kez okur ve sol sınır yalnızca ileriye doğru hareket eder; böylece tek bir geçişte her bitiş noktası için orada biten, tekrar içermeyen en uzun dizi bulunur.

Her alt dizgeyi kontrol et

Doğru, ama en büyük testlerde bitmiyor

Sezgi

Her başlangıç ve bitiş konumunu dene ve her alt dizgenin karakterlerini bir kümeye ekleyerek sınama yap; karakterlerden biri kümede zaten varsa dur. Her aday sınandığı için en uzun geçerli alt dizge gözden kaçmaz.

Yaklaşık n²/2 alt dizge vardır; n = 5 × 10^4 için bu sayı 1.25 × 10^9 olur ve bir sınama en fazla n karakter okuyabilir: O(n³). Burada bir sınama en fazla 63 karakter sonra durur, çünkü dizge yalnızca 62 farklı karakter içerir; ancak geriye yine de bir milyardan fazla sınama kalır.

Algoritma

best değerini 0 olarak ayarla.
Her başlangıç indeksi için, dizenin başlangıcından sonuna kadar olan her bitiş indeksi üzerinde döngü yap.
Alt dizenin karakterlerini teker teker boş bir kümeye ekle ve kümede zaten bulunan ilk karakterde dur.
Hiçbir karakter tekrarlanmadıysa ve alt dize best değerini geçiyorsa uzunluğunu kaydet.
best değerini döndür.

def lengthOfLongestSubstring(s):
    def has_no_repeat(start, end):
        seen = set()
        for k in range(start, end + 1):
            if s[k] in seen:
                return False
            seen.add(s[k])
        return True

    best = 0
    n = len(s)
    for start in range(n):
        for end in range(start, n):
            if has_no_repeat(start, end):
                best = max(best, end - start + 1)
    return best

Kümeyle kayan pencere

Sezgi

abc içinde tekrar yoksa, abcd dizisini test etmek için tek bir soru gerekir: d, a, b ve c arasında mı? Penceredeki karakterlerden oluşan bir küme bu soruyu hemen yanıtlar.

right değerini her seferinde bir adım ilerlet. Yeni karakter kümedeyse, önceki kopyası kaldırılana kadar soldan karakterleri çıkar; ardından onu ekle ve ölç. Karakterleri yalnızca gerektiğinde çıkarırsın; bu nedenle her right değeri için pencere, o noktada biten ve tekrar içermeyen en uzun dizidir; en iyi alt dize de bir yerde biter. Her karakter kümeye bir kez girer ve en fazla bir kez çıkar: O(n).

Algoritma

Boş bir kümeyle, left = 0 ve best = 0 ile başla.
right değişkenini her indeks üzerinde ilerlet.
s[right] kümedeyken s[left] öğesini kaldır ve left değişkenini bir adım ileri taşı.
s[right] öğesini kümeye ekle.
right - left + 1 değeri best değerini aşarsa, bu değeri kaydet.
best değerini döndür.

def lengthOfLongestSubstring(s):
    in_window = set()  # the characters between left and right
    left = 0
    best = 0
    for right in range(len(s)):
        # Shrink from the left until s[right] is no longer inside.
        while s[right] in in_window:
            in_window.remove(s[left])
            left += 1
        in_window.add(s[right])
        best = max(best, right - left + 1)
    return best

Son görülen dizine atlayan kayan pencere

Sezgi

left'in nereye gitmesi gerektiğini zaten biliyorsun: yeni karakterin önceki kopyasının bir sonrasına. Her karakterin son indeksini bir map'te veya karakter kodu başına bir yuva içeren bir dizide sakla; böylece left tek adımda oraya atlar.

Yalnızca bu indeks left değerine eşit veya ondan büyükse atla. Daha eski bir kopya zaten pencerenin dışındadır ve ona atlamak left'i geriye taşır. Her adımdaki pencere, set sürümünün oluşturduğu pencerenin aynısıdır ve artık her karakter tek arama, tek karşılaştırma ve tek yazma işlemi gerektirir.

Algoritma

Karakterden son indekse eşleştiren boş bir eşleme oluştur ve left = 0 ile best = 0 değerlerini ata.
right değerini her indeks üzerinde ilerlet ve oradaki ch karakterini oku.
ch en son left değerinde veya daha sonrasında görüldüyse, left değerini o indeksin bir fazlasına ayarla.
right değerini ch karakterinin son indeksi olarak kaydet.
right - left + 1 değeri best değerini geçiyorsa, onu kaydet.
best değerini döndür.

def lengthOfLongestSubstring(s):
    last_seen = {}
    start = 0
    best = 0
    for i, ch in enumerate(s):
        if ch in last_seen and last_seen[ch] >= start:
            start = last_seen[ch] + 1
        last_seen[ch] = i
        if i - start + 1 > best:
            best = i - start + 1
    return best

Tuzaklar ve uç durumlar

left işaretçisini geriye taşımak. abba dizgesinde, son a'ya ulaştığınızda 0 indeksindeki önceki a zaten pencerenin dışındadır. 1 indeksine atlamak ikinci b'yi yeniden pencereye alır ve 2 yerine 3 sonucunu verir.
Pencereyi right - left olarak saymak. Her iki uç da pencerenin içindedir, bu yüzden bir ekleyin.
Önce dizgedeki tüm harfleri küçük harfe çevirmek. Burada a ve A farklı karakterlerdir, bu yüzden aA uzunluğu 2'dir.
Yalnızca tekrar olduğunda ölçüm yapmak. z gibi tekrarı olmayan bir dizge bunu hiçbir zaman tetiklemez ve sonuç 0 olur.

Sıkça sorulan sorular3

Tekrarlayan Karakter İçermeyen En Uzun Alt Dizinin zaman karmaşıklığı nedir?

Kayan pencere, O(n) zamanda çalışır; burada n, dizenin uzunluğudur: sağ kenar her karakteri bir kez okur ve sol kenar yalnızca ileri doğru hareket eder. Ek alan O(k) kadardır; burada k, dizenin içerebileceği farklı karakterlerin sayısıdır; bu örnekte 62.

Son indeksler için bir hash map mi yoksa bir dizi mi kullanmalısın?

Her ikisi de O(n) zaman karmaşıklığına sahiptir. Buradaki gibi küçük ve sabit bir karakter kümesi olduğunda, karakter koduna göre indekslenen bir dizi karma işlemini önler ve daha hızlıdır.

Bir alt dize ile bir alt dizi arasındaki fark nedir?

Bir alt dize, coddycode içindeki ode gibi, yan yana duran karakterlerden oluşan bir bloktur. Bir alt dizi karakterleri atlayabilir; örneğin cdy. Bu problem bir alt dize istediği için iki ucu olan bir pencere işe yarar.

def lengthOfLongestSubstring(s):
    # Kodu buraya yazın

Test #1

Test #2

Test #3

Argüman

s = "coddycode"

Beklenen Çıktı

Longest Substring Without Repeating Characters

Fonksiyon

Kısıtlar

Örnekler

İpuçları

Çözüm

Her alt dizgeyi kontrol et

Kümeyle kayan pencere

Son görülen dizine atlayan kayan pencere

Tuzaklar ve uç durumlar

Sıkça sorulan sorular3

Benzer problemler