Longest Repeating Character Replacement

Q: En Uzun Tekrarlayan Karakter Değiştirme algoritmasının zaman karmaşıklığı nedir?

Tek pencereli çözüm, n'nin s uzunluğu olduğu durumda O(n) zamanda çalışır: right her harfi bir kez ziyaret eder ve left her adımda en fazla bir kez ilerler. O(1) ek alan kullanır: 26 sayaç ve birkaç tam sayı.

OrtaKayan pencere

+10

Sana büyük İngilizce harflerden oluşan bir s dizgesi ve bir k tam sayısı veriliyor. s dizgesinde en fazla k konum seçip her birindeki harfi başka herhangi bir büyük harfle değiştirebilirsin.

Değişikliklerinden sonra aynı harfin tekrarlarından oluşan en uzun alt dizenin, yani yan yana duran harflerin uzunluğunu döndür.

Fonksiyon

characterReplacement(s: string, k: integer) → integer

sstring: büyük harflerden oluşan dize
kinteger: değiştirebileceğiniz en fazla harf sayısı
Döndürürinteger: oluşturabileceğiniz, tekrarlanan tek bir harften oluşan en uzun alt dizenin uzunluğu

Kısıtlar

1 ≤ s.length ≤ 5 × 10⁴
s yalnızca büyük İngilizce harfler içerir.
0 ≤ k ≤ s.length

Örnekler

Girdi: s = "BAAACAB"k = 1
Çıktı: 5
Açıklama: C'yi A olarak değiştirin; 1'den 5'e kadar olan indekslerde AAAAA okunur. Altı harf için iki değişiklik gerekir: 0'dan 5'e kadar olan indekslerde bir B ve C bulunur; 1'den 6'ya kadar olan indekslerde ise C ve son B bulunur.

Girdi: s = "AABBBAB"k = 2
Çıktı: 6
Açıklama: ABBBAB içinde, 1'den 6'ya kadar olan indekslerde B olmayan tek harfler iki A olduğundan, iki değişiklik BBBBBB sonucunu verir. Dizgenin tamamında üç A ve dört B vardır, bu yüzden üç değişiklik gerekir.

Gönderirken +17 gizli test

Ek soru

s yalnızca 26 büyük harfi değil, herhangi bir karakteri tutabiliyorsa ne değişir?

İpuçları

Tek tek açın. Her biri biraz daha fazlasını gösterir.

3 ipucundan 0 açıldı

Çözüm

Bir alt dizgenin maliyeti açıkça görülür: uzunluğundan en sık kullanılan harfin sayısı çıkarılır. Zor olan, n² alt dizgenin tamamı için ödeme yapmamaktır. Kayan pencere, dizgeyi bir kez okur ve en iyi sürüm iki gerçeğe dayanır: pencerenin hiçbir zaman küçülmesi gerekmez ve en yüksek harf sayısının hiçbir zaman azalması gerekmez.

Her alt dizgeyi kontrol et

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

Sezgi

Bir alt dizgeyi düzelt. Hangi harfe dönüşmeli? Zaten en sık görünen harfe, çünkü diğer tüm harflerin değişmesi gerekir. Yani, en sık görünen harfin top kez geçtiği, uzunluğu len olan bir alt dizge için len - top değişiklik gerekir ve bu sayı en fazla k olduğunda alt dizge elde edilebilir.

Tüm alt dizgeleri dene. Her başlangıç konumu için bitişi her seferinde bir harf ilerlet ve harf başına bir sayaç tutarak ilerledikçe top değerini artır. Böylece her yeni alt dizgeyi baştan saymak yerine tek bir güncellemeyle değerlendirirsin. Her alt dizge kontrol edildiği için ulaşılabilir en uzun alt dizge gözden kaçmaz.

Yavaştır çünkü n uzunluğundaki bir dizgenin yaklaşık n²/2 alt dizgesi vardır. n = 5 × 10^4 için bu, zaman sınırının izin verdiğinden çok daha fazla olan 1.25 × 10^9 kontrol demektir.

Algoritma

best değerini 0 olarak ayarla.
Her başlangıç indeksi için 26 sayımı ve top değerini 0 olarak sıfırla.
end değerini başlangıçtan son indekse kadar ilerlet. s[end] değerini kendi sayımına ekle ve bu sayım artık en yüksekse top değerini artır.
end - start + 1 - top ≤ k ise alt diziye ulaşılabilir: uzunluğu best değerini geçiyorsa kaydet.
best değerini döndür.

def characterReplacement(s, k):
    n = len(s)
    best = 0
    for start in range(n):
        count = [0] * 26  # letters in s[start..end]
        top = 0           # count of the most common letter there
        for end in range(start, n):
            c = ord(s[end]) - ord('A')
            count[c] += 1
            top = max(top, count[c])
            # Every letter that is not the most common one must change.
            if end - start + 1 - top <= k:
                best = max(best, end - start + 1)
    return best

Her hedef harf için bir kayan pencere

Sezgi

Soruyu tersine çevir ve önce harfi seç. Son dizinin tamamı A ise soru şuna dönüşür: en fazla k tane A olmayan harf içeren en uzun alt dize nedir? Bu, klasik bir kayan pencere problemidir.

right değişkenini dize boyunca ilerlet ve penceredeki hedef harf olmayan harfleri say. Bu sayı k değerini aşınca, tekrar k olana kadar left değişkenini ilerlet. Bir pencereyi büyütmek yalnızca değiştirilecek harfler ekleyebilir; dolayısıyla maliyeti fazla olan bir pencere büyüdüğünde de maliyeti fazla kalır ve left hiçbir zaman geriye gitmek zorunda kalmaz. Her right değeri için tuttuğun pencere, o konumda biten en uzun geçerli penceredir.

Bunu 26 harfin tamamı için çalıştır ve en iyi uzunluğu sakla. Her çalıştırma O(n) sürer; dolayısıyla toplamda 26 geçiş yapılır ve n = 5 × 10^4 için yaklaşık 1.3 × 10^6 adım gerekir. Bu doğrusal bir süredir, ancak dizeyi 26 kez okur ve yalnızca alfabe küçük olduğu için işe yarar.

Algoritma

A'dan Z'ye kadar her hedef harf için left = 0 ve others = 0 ile bir pencere başlat.
right'ı dizenin üzerinde ilerlet. s[right] hedef değilse others'ı bir artır.
others > k olduğu sürece left'i ilerlet ve pencereden çıkan harf hedef değilse others'tan bir çıkar.
right - left + 1 değeri best'ten büyükse bu değeri kaydet.
26 harfin tamamını işledikten sonra best'i döndür.

def characterReplacement(s, k):
    best = 0
    for target in "ABCDEFGHIJKLMNOPQRSTUVWXYZ":
        left = 0
        others = 0  # letters in s[left..right] that are not target
        for right in range(len(s)):
            if s[right] != target:
                others += 1
            # Too many letters to change: drop letters from the left.
            while others > k:
                if s[left] != target:
                    others -= 1
                left += 1
            best = max(best, right - left + 1)
    return best

Hiç küçülmeyen bir pencere

Sezgi

Bir penceredeki her harfi ele al. İçindeki 26 harfin her biri için bir sayaç ve en yüksek sayaç olan top değerini tut. Pencere için length - top değişiklik gerekir; bu değer en fazla k olduğunda pencere uygundur.

İlk bilgi: Pencerenin hiçbir zaman küçülmesi gerekmez. Yalnızca şimdiye kadar bulunan en iyi uzunluğu geçmek istediğinden, s[right] eklemek pencereyi fazla maliyetli hâle getirdiğinde soldan bir harfi çıkar. Pencere bir adım kayar ve uzunluğunu korur. Pencere fazla maliyetli olmadığında bir harf büyür. Bu nedenle uzunluğu, şimdiye kadar bulunan en iyi uzunluğa eşittir ve sonunda yanıt n - left olur.

İkinci bilgi: top değerinin hiçbir zaman azalması gerekmez. Soldan bir harf çıkarken top değerini değiştirmezsin; bu yüzden pencerenin içindeki gerçek sayıdan yüksek olabilir. Bu sorun değildir. Bir kaydırmadan sonra pencerenin uzunluğu tam olarak top + k olur; dolayısıyla pencereyi büyütmek için içinde top + 1 kez görünen bir harf gerekir ve o anda top da onunla birlikte yükselir. Eski kalmış bir top değeri pencerenin kaymasına neden olabilir, ancak yanlışlıkla büyümesine asla neden olmaz; ayrıca kaydırmak hiçbir şeyi kaybettirmez, çünkü rekoru yalnızca daha uzun bir pencere geçebilir.

k = 1 iken BAAACAB dizisinde pencere BAAA olacak şekilde büyür; ardından BAAAC için 2 değişiklik gerektiğinden pencere AAAC olacak şekilde kayar. Sonraki A eklenince top 4'e yükselir ve pencere AAACA olacak şekilde, uzunluğu 5'e çıkar. Son B pencerenin bir kez daha kaymasına neden olur; dolayısıyla yanıt 5'tir.

Algoritma

26 sayısını, left = 0 ve top = 0 değerlerini koruyun.
right değerini dizge boyunca ilerletin: s[right] değerini sayısına ekleyin ve bu sayı artık daha yüksekse top değerini artırın.
right - left + 1 - top > k ise pencere çok fazla değişiklik gerektiriyor demektir: s[left] değerini sayımlardan çıkarın ve left değerini bir adım ilerletin. Pencere kayar ve uzunluğunu korur.
Bir harf ayrıldığında top değerini asla düşürmeyin.
Son pencere uzunluğunu, n - left değerini döndürün.

def characterReplacement(s, k):
    count = [0] * 26  # letters inside the window s[left..right]
    left = 0
    top = 0  # the highest count any letter has reached in a window
    for right in range(len(s)):
        c = ord(s[right]) - ord('A')
        count[c] += 1
        top = max(top, count[c])
        # Needs more than k changes: slide the window instead of growing it.
        if right - left + 1 - top > k:
            count[ord(s[left]) - ord('A')] -= 1
            left += 1
    # The window only grew when a longer valid substring was found.
    return len(s) - left

Tuzaklar ve uç durumlar

Pencere kodu kısadır; bu yüzden yanlış yanıtların çoğu maliyet formülünden ya da yalnızca doğruymuş gibi görünen bir kestirmeden kaynaklanır.

En uzun ardışık diziye k eklemek. k = 3 olan AAAB örneğinde bu, dizgeden daha uzun olan 6 sonucunu verir. k = 1 olan BAAACAB örneğinde ise 4 sonucunu verir; ancak doğru değişiklik ortada yapılır ve iki diziyi birleştirerek 5 uzunluğunda bir dizi oluşturur.
Penceredeki en sık geçen harf yerine pencerenin ilk harfine göre değişiklikleri saymak. BAAA penceresinde üç değil, bir değişiklik gerekir.
Penceresinin küçülebildiği bir sürümde n - left döndürmek. Bu kestirme yalnızca pencere hiç kısalmadığında geçerlidir; buradaki tek pencereli kodda olduğu gibi. Döngünüz pencereyi while ile küçültüyor ve gerçek maksimumu yeniden hesaplıyorsa ayrı bir best değişkeni tutun.
Pencere uzunluğunu right - left olarak hesaplamak. Her iki uç da pencerenin içinde olduğundan sonuca bir ekleyin.
k = 0 için özel durum tanımlamak. Hiç değişiklik yapmadan da pencere kuralı, tek bir harften oluşan en uzun ardışık diziyi zaten döndürür.

Sıkça sorulan sorular4

En Uzun Tekrarlayan Karakter Değiştirme algoritmasının zaman karmaşıklığı nedir?

Tek pencereli çözüm, n'nin s uzunluğu olduğu durumda O(n) zamanda çalışır: right her harfi bir kez ziyaret eder ve left her adımda en fazla bir kez ilerler. O(1) ek alan kullanır: 26 sayaç ve birkaç tam sayı.

Maksimum frekans, pencere kaydığında neden güncellenmek zorunda değildir?

Pencere yalnızca kendi rekorunu geçmeye çalışıyor. Bir kaydırmadan sonra uzunluğu top + k olur; bu nedenle daha uzun, geçerli bir pencere için bir harfin top kereden fazla görünmesi gerekir ve bu da zaten top değerini artırır. Gereğinden yüksek bir top yalnızca pencerenin uzunluğunu korur; pencerenin olmaması gereken durumlarda büyümesine asla neden olmaz.

Bu, Tekrarlayan Karakterler Olmadan En Uzun Alt Dize probleminden nasıl farklıdır?

İkisi de dize üzerinde iki kenarı hareket ettirir, ancak geçerli bir pencerenin kuralı farklıdır. Orada, hiçbir karakter tekrarlanmadığında pencere geçerlidir ve tekrar ortadan kalkana kadar küçülmesi gerekir. Burada ise uzunluğundan en sık görülen harfin sayısı çıkarıldığında sonuç en fazla k olduğunda pencere geçerlidir; bu da pencerenin küçülmek yerine sabit uzunlukta kaydırılmasını sağlar.

Bu problem ikili aramayla çözülebilir mi?

Evet. Uzunluğu L olan bir alt dizgeye ulaşılabiliyorsa, içindeki daha kısa her alt dizgeye de ulaşılabilir; bu nedenle L üzerinde ikili arama yapabilirsin. Her L için bu uzunlukta sabit bir pencere kaydır ve herhangi bir konumun en fazla k değişiklik gerektirip gerektirmediğini kontrol et. Bu, O(n log n) karmaşıklığındadır; tek pencereli çözümden daha yavaştır ama verilebilecek makul bir yanıttır.

Python

def characterReplacement(s, k):
    # Kodu buraya yazın

Test durumları

Durum 1

Durum 2

Durum 3

Girdi

s = "BAAACAB"
k = 1

Beklenen

Longest Repeating Character Replacement

Fonksiyon

Kısıtlar

Örnekler

İpuçları

Çözüm

Her alt dizgeyi kontrol et

Her hedef harf için bir kayan pencere

Hiç küçülmeyen bir pencere

Tuzaklar ve uç durumlar

Sıkça sorulan sorular4

Benzer problemler