Longest Repeating Character Replacement

Q: En Uzun Tekrarlayan Karakter Değiştirme işleminin 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

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

Değişikliklerinden sonra aynı harfin tekrarlandığı en uzun alt dizgenin (yan yana duran harf dizisinin) 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ğin, aynı harfin tekrarlandığı en uzun alt dizenin uzunluğu

Kısıtlar

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

Örnekler

Girdi: s = "BAAACAB"k = 1
Çıktı: 5
Açıklama: C'yi A olarak değiştirmek, 1'den 5'e kadar olan indislerin AAAAA olarak okunmasını sağlar. Her iki altı harfli pencere de bir B ve C içerir, bu yüzden iki değişiklik gerekir.

Girdi: s = "AABBBAB"k = 2
Çıktı: 6
Açıklama: 1'den 6'ya kadar olan indeksler ABBBAB değerini içerir ve her iki A harfini değiştirmek BBBBBB sonucunu verir. Tüm dizgede yedi harf arasında yalnızca dört B harfi vardır, bu yüzden üç değişiklik gerekir.

Ek soru

s 26 büyük harf yerine herhangi bir karakteri tutabilirse 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 dizenin en sık geçen harfini koruyup geri kalanını değiştirin: En sık geçen harfin top kez göründüğü, uzunluğu len olan bir alt dize için len - top değişiklik gerekir. Kayar pencere, len - top ≤ k koşulunu sağlayan en uzun alt dizeyi tek geçişte bulur; çünkü pencerenin hiçbir zaman küçülmesi gerekmez ve top hiçbir zaman azalmaz.

Her alt dizeyi kontrol edin

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

Sezgi

Her başlangıç için bitişi her seferinde bir harf artırın, her harfin sayısını ve top değerini güncelleyin ve len - top ≤ k koşulunu test edin. Her yeni alt dize, baştan sayım yapmak yerine tek bir güncelleme gerektirir ve her alt dize kontrol edildiğinden, ulaşılabilecek en uzun alt dize gözden kaçmaz.

n uzunluğundaki bir dizenin yaklaşık n²/2 alt dizisi vardır: n = 5 × 10^4 için 1.25 × 10^9 kontrol.

Algoritma

best değerini 0 olarak ayarla.
Her başlangıç indeksi için 26 sayacı ve top değerini 0 olarak sıfırla.
end değerini başlangıçtan son indekse kadar ilerlet. s[end] değerini kendi sayacına ekle ve bu sayaç artık en yüksek değerdeyse top değerini artır.
end - start + 1 - top ≤ k ise, best değerini geçiyorsa uzunluğu 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

Hedef harf başına bir kayan pencere

Sezgi

Önce hedef harfi seç. Sonuçta tüm dize A olursa, en fazla k tane A olmayan harf içeren en uzun alt dizeyi istersin.

right işaretçisini dize boyunca ilerlet ve penceredeki hedef olmayan harfleri say. Sayı k'yi aştığında, tekrar k olana kadar left işaretçisini ilerlet. Maliyeti fazla olan bir pencere büyüdükçe maliyeti yine fazla kalır; bu yüzden left asla geriye gitmez ve her right için pencere, o konumda biten en uzun geçerli penceredir.

Bunu 26 harfin tümü için çalıştır ve en iyisini sakla: en fazla 5 × 10^4 harf üzerinde 26 doğrusal geçiş. Yalnızca alfabe küçük olduğu için O(n) kalır.

Algoritma

A'dan Z'ye kadar her hedef harf için left = 0 ve others = 0 ile bir pencere başlat.
right'ı dizge boyunca ilerlet. s[right] hedef değilse others'ı bir artır.
others > k olduğu sürece left'i ilerlet; çıkan harf hedef değilse others'ı bir azalt.
right - left + 1 değeri best'i geçiyorsa bu değeri kaydet.
26 harfin tamamından 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

Pencere için 26 sayımını ve en yüksek sayı olan top değerini tut. s[right] eklendiğinde pencereyi maliyet açısından fazla pahalı hâle getirirse soldan bir harfi çıkar: pencere kayar ve uzunluğunu korur; çünkü rekoru yalnızca daha uzun bir pencere geçebilir. Aksi hâlde pencere bir birim büyür. Uzunluğu her zaman şimdiye kadarki en iyi uzunluktur, dolayısıyla yanıt n - left olur.

Bir harf pencereden çıktığında, artık gerçek sayıdan yüksek olsa bile top değerini değiştirme. Kaydırmadan sonra uzunluk tam olarak top + k olur; bu nedenle pencerenin büyümesi için bir harfin top + 1 kez görünmesi gerekir ve o anda top da onunla birlikte yükselir. Eski bir top değeri pencerenin yalnızca kaymasına neden olabilir; kaydırma ise rekoru düşüremez.

k = 1 iken BAAACAB dizisinde BAAAC için 2 değişiklik gerekir ve pencere AAAC olacak şekilde kayar. Sonraki A, top değerini 4'e çıkarır ve pencere uzunluğu 5 olan AAACA hâline gelir.

Algoritma

26 sayısını, left = 0 değerini ve top = 0 değerini tut.
right değerini dizge üzerinde ilerlet: s[right] değerini sayısına ekle ve bu sayı artık daha yüksekse top değerini artır.
right - left + 1 - top > k ise s[left] değerini sayımlardan çıkar ve left değerini bir adım ilerlet. top değerini asla düşürme.
Son pencere uzunluğunu, n - left, döndür.

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

k değerini en uzun diziye eklemek. k = 3 iken AAAB için bu, dizgeden daha uzun olan 6 sonucunu verir. k = 1 iken BAAACAB için 4 sonucunu verir, ancak C değiştirilince iki dizi birleşerek 5 olur.
Değişiklikleri, pencerenin en sık görülen harfi yerine ilk harfine göre saymak. BAAA için üç değil, bir değişiklik gerekir.
Pencereyi while ile daraltan ve gerçek maksimumu yeniden hesaplayan bir döngüden n - left döndürmek. Bu pencere küçülür; bu yüzden ayrı bir best tut.
Pencereyi right - left olarak ölçmek. Her iki uç da pencerenin içinde olduğundan bir ekle.

Sıkça sorulan sorular3

En Uzun Tekrarlayan Karakter Değiştirme işleminin 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ı.

Bu, Tekrarlanan Karakter İçermeyen En Uzun Alt Dizeden 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 tekrarlanamaz; bu yüzden tekrar ortadan kalkana kadar pencere daralır. Burada ise uzunluk eksi en yüksek sayı k değerinden küçük veya eşit olmalıdır; bu nedenle pencere sabit uzunlukta kayabilir.

Bu problem ikili aramayla çözülebilir mi?

Evet. Uzunluğu L olan bir alt diziye ulaşılabiliyorsa, içindeki daha kısa her alt diziye de ulaşılabilir; bu nedenle L üzerinde ikili arama yapabilirsiniz. Her L için, bu uzunluktaki sabit bir pencereyi kaydırın ve herhangi bir konum için en fazla k değişiklik gerekip gerekmediğini kontrol edin. Bu O(n log n) olur ve tek pencereli çözümden daha yavaştır.

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

Test #1

Test #2

Test #3

Argümanlar

s = "BAAACAB"
k = 1

Beklenen Çıktı

Longest Repeating Character Replacement

Fonksiyon

Kısıtlar

Örnekler

İpuçları

Çözüm

Her alt dizeyi kontrol edin

Hedef harf başına bir kayan pencere

Hiç küçülmeyen bir pencere

Tuzaklar ve uç durumlar

Sıkça sorulan sorular3

Benzer problemler