Longest Repeating Character Replacement

+10

Kamu mendapatkan string s yang berisi huruf besar bahasa Inggris dan bilangan bulat k. Kamu boleh memilih paling banyak k posisi pada s dan mengubah huruf di setiap posisi tersebut menjadi huruf besar lainnya.

Kembalikan panjang substring terpanjang, yaitu rangkaian huruf yang bersebelahan, yang berisi satu huruf berulang setelah perubahanmu.

Fungsi

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

sstring: string yang terdiri dari huruf kapital
kinteger: jumlah huruf terbanyak yang boleh kamu ubah
Mengembalikaninteger: panjang substring terpanjang yang bisa kamu buat dengan satu huruf yang diulang

Batasan

1 ≤ s.length ≤ 5 × 10⁴
s hanya berisi huruf kapital bahasa Inggris.
0 ≤ k ≤ s.length

Contoh

Input: s = "BAAACAB"k = 1
Output: 5
Penjelasan: Mengubah C menjadi A membuat indeks 1 hingga 5 terbaca AAAAA. Kedua jendela enam huruf berisi B dan C, jadi keduanya memerlukan dua perubahan.

Input: s = "AABBBAB"k = 2
Output: 6
Penjelasan: Indeks 1 sampai 6 berisi ABBBAB, dan mengubah kedua huruf A menghasilkan BBBBBB. Seluruh string hanya memiliki empat huruf B dari tujuh huruf, jadi diperlukan tiga perubahan.

Pertanyaan lanjutan

Apa yang berubah jika s dapat menyimpan karakter apa pun, bukan hanya 26 huruf kapital?

Petunjuk

Buka satu per satu. Setiap petunjuk mengungkap sedikit lebih banyak.

0 dari 3 dibuka

Solusi

Pertahankan huruf yang paling sering muncul dalam substring dan ubah sisanya: substring dengan panjang len yang huruf paling sering munculnya sebanyak top kali membutuhkan len - top perubahan. Sliding window menemukan substring terpanjang dengan len - top ≤ k dalam satu kali lintasan, karena window tidak perlu mengecil dan top tidak pernah berkurang.

Periksa setiap substring

Benar, tetapi tidak selesai pada tes terbesar

Intuisi

Untuk setiap posisi awal, perpanjang posisi akhir satu huruf setiap kali, perbarui hitungan untuk setiap huruf dan top, lalu uji len - top ≤ k. Setiap substring baru hanya memerlukan satu pembaruan, bukan penghitungan ulang, dan setiap substring diperiksa, jadi substring terpanjang yang bisa dijangkau tidak akan terlewat.

String dengan panjang n memiliki sekitar n²/2 substring: 1.25 × 10^9 pemeriksaan untuk n = 5 × 10^4.

Algoritma

Atur best ke 0.
Untuk setiap indeks awal, reset 26 hitungan dan top ke 0.
Pindahkan end dari indeks awal hingga indeks terakhir. Tambahkan s[end] ke hitungannya dan naikkan top jika hitungan itu kini menjadi yang tertinggi.
Jika end - start + 1 - top ≤ k, simpan panjangnya jika melebihi best.
Kembalikan best.

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

Satu jendela geser untuk setiap huruf target

Intuisi

Pilih huruf terakhir terlebih dahulu. Jika rentetannya berakhir dengan semua huruf A, kamu ingin mencari substring terpanjang yang memiliki paling banyak k huruf yang bukan A.

Geser right sepanjang string dan hitung jumlah huruf yang bukan target di dalam window. Saat jumlahnya melebihi k, geser left ke depan sampai jumlahnya kembali menjadi k. Window yang terlalu mahal akan tetap terlalu mahal saat membesar, jadi left tidak pernah bergerak mundur, dan untuk setiap right, window tersebut adalah window valid terpanjang yang berakhir di posisi itu.

Jalankan untuk semua 26 huruf dan simpan hasil terbaik: 26 lintasan linear untuk hingga 5 × 10^4 huruf. Kompleksitasnya tetap O(n) hanya karena alfabetnya kecil.

Algoritma

Untuk setiap huruf target dari A hingga Z, mulai sebuah jendela dengan left = 0 dan others = 0.
Gerakkan right sepanjang string. Jika s[right] bukan huruf target, tambahkan satu ke others.
Selama others > k, gerakkan left ke depan, kurangi satu jika huruf yang keluar bukan huruf target.
Simpan right - left + 1 jika nilainya lebih besar daripada best.
Setelah memeriksa semua 26 huruf, kembalikan best.

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

Satu jendela yang tidak pernah mengecil

Intuisi

Simpan 26 hitungan untuk window dan top, yaitu hitungan tertinggi. Saat menambahkan s[right] membuat window terlalu mahal, buang satu huruf di sebelah kiri: window bergeser dan panjangnya tetap, karena hanya window yang lebih panjang yang bisa mengalahkan rekor. Jika tidak, panjangnya bertambah satu. Panjangnya selalu sama dengan yang terbaik sejauh ini, jadi jawabannya adalah n - left.

Saat sebuah huruf keluar, biarkan top tetap, meskipun nilainya kini lebih tinggi daripada hitungan sebenarnya. Setelah bergeser, panjangnya tepat top + k, jadi agar bisa bertambah, suatu huruf harus muncul top + 1 kali, dan top naik pada saat itu. Nilai top yang sudah kedaluwarsa hanya bisa membuat window bergeser, dan pergeseran tidak bisa menghilangkan rekor.

Pada BAAACAB dengan k = 1, BAAAC memerlukan 2 perubahan dan bergeser menjadi AAAC. Huruf A berikutnya menaikkan top menjadi 4 dan window bertambah menjadi AAACA, dengan panjang 5.

Algoritma

Pertahankan hitungan untuk 26 huruf, left = 0 dan top = 0.
Geser right sepanjang string: tambahkan s[right] ke hitungannya dan naikkan top jika hitungan itu kini lebih tinggi.
Jika right - left + 1 - top > k, hapus s[left] dari hitungan dan geser left satu langkah. Jangan pernah menurunkan top.
Kembalikan panjang window akhir, n - left.

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

Jebakan dan kasus tepi

Menambahkan k pada rangkaian terpanjang. Dalam AAAB dengan k = 3, hasilnya 6, lebih panjang daripada string. Dalam BAAACAB dengan k = 1, hasilnya 4, tetapi mengubah C menggabungkan dua rangkaian menjadi 5.
Menghitung perubahan berdasarkan huruf pertama dalam window, bukan huruf yang paling sering muncul. BAAA memerlukan satu perubahan, bukan tiga.
Mengembalikan n - left dari perulangan yang memperkecil window dengan while dan menghitung ulang nilai maksimum sebenarnya. Window tersebut menjadi lebih pendek, jadi simpan best secara terpisah.
Mengukur window sebagai right - left. Kedua ujungnya termasuk di dalamnya, jadi tambahkan satu.

Pertanyaan yang sering diajukan3

Apa kompleksitas waktu dari Longest Repeating Character Replacement?

Solusi satu jendela berjalan dalam waktu O(n), dengan n sebagai panjang s: right mengunjungi setiap huruf satu kali dan left bergerak paling banyak satu kali per langkah. Solusi ini menggunakan ruang tambahan O(1), yaitu 26 hitungan dan beberapa bilangan bulat.

Apa bedanya ini dengan substring terpanjang tanpa karakter berulang?

Keduanya bergerak melewati string sebanyak dua sisi, tetapi aturan untuk window yang baik berbeda. Pada kasus itu, tidak boleh ada karakter yang berulang, jadi window menyusut sampai tidak ada lagi karakter yang berulang. Di sini, panjang dikurangi jumlah tertinggi harus paling banyak k, jadi window dapat bergeser dengan panjang tetap.

Apakah masalah ini bisa diselesaikan dengan pencarian biner?

Ya. Jika substring dengan panjang L dapat dicapai, semua substring yang lebih pendek di dalamnya juga dapat dicapai, jadi kamu bisa melakukan pencarian biner pada L. Untuk setiap L, geser jendela tetap sepanjang itu dan periksa apakah ada posisi yang membutuhkan paling banyak k perubahan. Kompleksitasnya O(n log n), lebih lambat daripada solusi satu jendela.

def characterReplacement(s, k):
    # Tulis kodemu di sini

Tes #1

Tes #2

Tes #3

Argumen

s = "BAAACAB"
k = 1

Output yang diharapkan

Longest Repeating Character Replacement

Fungsi

Batasan

Contoh

Petunjuk

Solusi

Periksa setiap substring

Satu jendela geser untuk setiap huruf target

Satu jendela yang tidak pernah mengecil

Jebakan dan kasus tepi

Pertanyaan yang sering diajukan3

Soal serupa