Sliding window variabel

Jendela tetap menggeser kedua batasnya bersamaan, sedangkan pola pada topik ini melepaskan ukuran jendela dan menentukan batasnya lewat kondisi. Sliding window variabel memakai dua gerakan, expand saat batas kanan menerima elemen baru, dan shrink saat batas kiri melepaskannya, sehingga lebar jendela naik turun mengikuti keadaan data. Setelah topik ini, dua keluarga soal klasik dapat diselesaikan dalam satu lintasan $O(n)$, yaitu substring terpanjang tanpa karakter berulang serta subarray terpendek dengan jumlah minimal. Substring adalah potongan teks yang berurutan, sedangkan subarray adalah potongan array yang berurutan. Topik ini juga memberi panduan memilih jendela tetap atau variabel berdasarkan bunyi soal.

Dua gerakan pada satu jendela#

Dua batas jendela variabel bergerak dengan kebebasan yang berbeda. Batas kanan wajib maju satu langkah pada setiap putaran, karena elemen baru harus terus dicoba, sedangkan batas kiri hanya maju ketika kondisi jendela terlanggar atau ketika jawaban yang lebih pendek sedang dicari. Lebar jendela karenanya bukan angka tetap, melainkan hasil tarik-menarik antara keinginan melebar dan tuntutan kondisi.

Diagram berikut merangkum kedua gerakan itu pada satu baris data.

Kotak hijau menandai jendela yang sah pada suatu saat, panah kiri adalah shrink yang menyelamatkan kondisi, dan panah kanan adalah expand yang terus mencoba elemen baru. Jatah gerakan keduanya pun ketat: batas kanan maju tepat $n$ kali sepanjang perulangan, sedangkan batas kiri tidak pernah mundur, sehingga total langkah kedua batas paling banyak $2n$ meskipun lebar jendelanya naik turun. Angka itulah yang menjadi dasar klaim $O(n)$ pada kedua demo bagian berikutnya. Yang membedakan satu soal dengan soal lainnya hanyalah kondisi jendelanya, jumlah minimal, karakter tanpa pengulangan, atau batasan lain yang disebut pada soal.

Substring terpanjang tanpa karakter berulang#

Soalnya berbunyi: cari substring terpanjang yang seluruh karakternya berbeda. Kondisi jendelanya jelas, tidak ada huruf yang muncul dua kali. Pemegang kondisinya adalah peta frekuensi berupa dict Python, yaitu struktur pemetaan kunci ke nilai. Batas kanan selalu maju dan menambah hitungan huruf barunya, kemudian selama huruf itu berhitung dua, batas kiri maju melepaskan isi jendela satu per satu.

# Substring terpanjang tanpa karakter berulang: jendela variabel
# dengan peta frekuensi sebagai pemegang kondisi.

def substring_terpanjang(teks):
    frekuensi = {}
    kiri = 0
    terbaik = 0
    terbaik_isi = ""
    for kanan in range(len(teks)):
        huruf = teks[kanan]
        frekuensi[huruf] = frekuensi.get(huruf, 0) + 1
        while frekuensi[huruf] > 1:            # kondisi dilanggar: susutkan
            kiri_huruf = teks[kiri]
            frekuensi[kiri_huruf] -= 1
            if frekuensi[kiri_huruf] == 0:
                del frekuensi[kiri_huruf]
            kiri += 1
        if kanan - kiri + 1 > terbaik:
            terbaik = kanan - kiri + 1
            terbaik_isi = teks[kiri:kanan + 1]
    return terbaik, terbaik_isi

teks_uji = ["kabcdabc", "bananas", "abab", "abcdefghij"]
for teks in teks_uji:
    panjang, isi = substring_terpanjang(teks)
    print(f"{teks:12} -> {panjang} ('{isi}')")

kabcdabc     -> 5 ('kabcd')
bananas      -> 3 ('ban')
abab         -> 2 ('ab')
abcdefghij   -> 10 ('abcdefghij')

Kata kabcdabc menghasilkan 5 dengan isi kabcd, karena huruf a yang kedua memaksa shrink sebelum penelusuran berlanjut. Kata bananas berhenti pada 3 dengan isi ban, dan abcdefghij yang seluruh hurufnya unik mempertahankan jendela penuh sepanjang sepuluh karakter. Peta frekuensi pada demo sengaja dikosongkan dari entri bernilai nol, sehingga banyaknya kunci selalu sama dengan banyaknya huruf berbeda di dalam jendela. Pembacaan kondisinya pun lurus: satu huruf yang berhitung dua adalah satu pelanggaran, dan tidak ada penghitungan lain yang perlu dijaga. Biaya totalnya $O(n)$ meskipun terdapat perulangan di dalam perulangan, karena setiap huruf masuk jendela paling banyak satu kali lewat expand dan keluar paling banyak satu kali lewat shrink, sehingga total gerakan kedua batas tidak pernah melebihi $2n$.

Subarray terpendek dengan jumlah minimal#

Soal kebalikannya mencari jendela terpendek yang jumlahnya mencapai target. Kondisi jendela berbunyi jumlah minimal target, sehingga setiap kali kondisi terpenuhi, jawaban dicatat dan jendela segera menyusut untuk mencoba versi yang lebih pendek. Urutan catat lalu susut ini kebalikan dari soal terpanjang, karena jawaban justru hidup pada jendela yang sedang sah sebelum dihancurkan oleh shrink.

# Subarray terpendek dengan jumlah minimal target: jendela variabel
# yang mencatat jawaban sebelum menyusut.

def subarray_terpendek(data, target):
    kiri = 0
    jumlah = 0
    terbaik = None
    isi = None
    for kanan in range(len(data)):
        jumlah += data[kanan]              # expand: terima elemen baru
        while jumlah >= target:            # kondisi terpenuhi
            panjang = kanan - kiri + 1
            if terbaik is None or panjang < terbaik:
                terbaik = panjang
                isi = data[kiri:kanan + 1]
            jumlah -= data[kiri]           # shrink: lepas elemen kiri
            kiri += 1
    return terbaik, isi

data = [5, 1, 3, 6, 2, 8, 4]
target = 11
panjang, isi = subarray_terpendek(data, target)
print("data   :", data)
print("target :", target)
print("panjang subarray terpendek:", panjang)
print("isi jendela terbaik       :", isi)

data   : [5, 1, 3, 6, 2, 8, 4]
target : 11
panjang subarray terpendek: 2
isi jendela terbaik       : [8, 4]

Jawabannya panjang 2 dengan isi [8, 4], karena jumlahnya 12 mencapai target 11 dan tidak ada jendela satu elemen yang mampu begitu. Jendela [5, 1, 3, 6] berpanjang 4 menjadi jawaban pertama yang tercatat, lalu berturut-turut digantikan kandidat yang lebih pendek setelah beberapa kali shrink. Perulangan while di dalamnya boleh berjalan beberapa kali pada satu expand, karena satu elemen baru bisa membuat beberapa elemen kiri sekaligus tidak diperlukan lagi. Hanya nilai positif yang membuat penyusutan aman di sini, karena melepas elemen positif pasti menurunkan jumlah jendela.

Memilih jendela tetap atau variabel#

Bunyi soal hampir selalu memberi tahu pola mana yang dipakai. Ketika ukurannya disebut eksplisit, subarray $k$ elemen atau jendela $k$ hari terakhir, jendela tetap langsung menjadi pilihannya karena kedua batas bergerak bersama. Ketika yang disebut justru kondisi kualitatif, tanpa pengulangan, jumlah minimal, atau paling banyak $m$ karakter berbeda, jendelanya variabel dan kondisi itu dititipkan pada struktur pemegang kondisi seperti peta frekuensi.

Tabel berikut merangkum perbedaan keputusannya.

Kedua pola berbagi kerangka yang sama, dan templat berikut merangkum jendela variabelnya.

# tidak-dijalankan
kiri = 0
for kanan in range(len(data)):
    # expand: terima data[kanan], mutakhirkan pemegang kondisi
    ...
    while kondisi_terlanggar:   # atau kondisi_terpenuhi untuk soal terpendek
        # shrink: lepas data[kiri], majukan kiri
        ...
    # catat jawaban di baris ini untuk soal terpanjang

Batas kanan dalam for menjamin expand berjalan $n$ kali, sedangkan while mengurus shrink yang totalnya juga tidak melebihi $n$. Baris pencatatan jawaban berpindah posisi menurut jenis soalnya, sebelum while untuk soal terpendek dan sesudahnya untuk soal terpanjang.

Soal untuk dipraktikkan#

Delapan soal berikut menguji pola dua penunjuk maupun jendela geser yang dipakai sepanjang modul ini.

1. Valid Palindrome : pemeriksaan simetris dua penunjuk dari topik two pointer, dengan tambahan penyaringan karakter yang bukan huruf maupun angka.
2. Two Sum II - Input Array Is Sorted : wujud resmi dari demo array terurut, dengan dasar keputusan urutan yang sama persis.
3. Container With Most Water : konvergensi dua ujung yang menguji dasar keputusan dengan membuang sisi yang lebih pendek agar tidak ada kandidat terlewat.
4. Move Zeroes : dua penunjuk searah yang mempertahankan urutan, saudara dari gerakan expand pada jendela.
5. Find the Duplicate Number : array diperlakukan sebagai fungsi penerus lalu siklusnya dideteksi dengan pointer cepat dan lambat ala Floyd.
6. Longest Substring Without Repeating Characters : wujud resmi dari demo substring terpanjang dengan peta frekuensi dan gerakan shrink.
7. Minimum Size Subarray Sum : subarray terpendek dengan jumlah minimal target, persis pola catat-lalu-susut pada topik ini.
8. Minimum Window Substring : jendela variabel paling menantang dengan dua peta frekuensi, melatih pemeriksaan kondisi jendela sah secara teliti.

Ringkasan#

• Jendela variabel menggantikan ukuran tetap dengan kondisi, expand menerima elemen baru setiap putaran, dan shrink memulihkan kondisi dengan melepas isi kiri.
• Peta frekuensi memegang kondisi substring terpanjang tanpa pengulangan, dan total gerakan kedua batas tidak melebihi $2n$ sehingga biayanya tetap $O(n)$.
• Soal terpendek mencatat jawaban sebelum menyusut, sedangkan soal terpanjang mencatat setelah jendela kembali sah.
• Ukuran eksplisit pada bunyi soal menunjuk jendela tetap, sedangkan kondisi kualitatif menunjuk jendela variabel.

Referensi#

• Built-in Types — Python Software Foundation — dokumentasi tipe pemetaan (dict) yang dipakai sebagai peta frekuensi pada demo.
• NeetCode Roadmap — NeetCode — peta latihan dengan kategori sliding window yang memuat keluarga soal jendela variabel.