Sliding Window

Sliding window adalah teknik yang memanfaatkan sifat kontigu array untuk menemukan subarray optimal tanpa harus mengevaluasi semua kemungkinan subarray. Bayangkan kita mencari jumlah maksimum dari k elemen berurutan — naif: cek setiap window berukuran k dengan loop O(n·k). Sliding window: hitung ulang hanya sel yang masuk dan keluar — O(n). Pada Chapter ini kita akan mempelajari dua varian: fixed-size window (ukuran tetap) dan variable-size window (ukuran menyesuaikan kondisi). Kedua varian adalah senjata utama untuk soal substring/subarray optimal.

Intuisi: Mengapa O(n)? #

Mekanisme: Hindari Recomputasi #

Misalkan window saat ini berisi a[i..i+k-1] dengan jumlah S. Saat kita geser ke window berikutnya a[i+1..i+k], kita tidak perlu menjumlahkan ulang seluruh elemen. Yang berubah hanya:

Elemen yang keluar: a[i] — kurangi S -= a[i]
Elemen yang masuk: a[i+k] — tambah S += a[i+k]

Dua operasi per geseran — total O(n) untuk seluruh iterasi. Inilah esensi sliding window: memanfaatkan overlap antar window berturut-turut.

flowchart LR W0["window 0: a[0..2]"] -->|"keluar a[0], masuk a[3]"| W1["window 1: a[1..3]"] W1 -->|"keluar a[1], masuk a[4]"| W2["window 2: a[2..4]"]

Fixed-Size Window: Maximum Sum Subarray Size K #

Aturan #

Diberikan array a berukuran n dan integer k, cari jumlah maksimum dari subarray berukuran tepat k.

Kode: Fixed-Size Sliding Window #

cpp
#include <iostream>
#include <vector>
#include <algorithm>
#include <limits>

long long max_sum_k(const std::vector<int>& a, int k) {
    int n = static_cast<int>(a.size());
    if (k > n) return 0;  // tidak ada window valid

    long long current = 0;
    for (int i = 0; i < k; ++i) current += a[i];   // window awal

    long long best = current;
    for (int i = k; i < n; ++i) {
        current += a[i] - a[i - k];                  // geser window
        best = std::max(best, current);
    }
    return best;
}

int main() {
    std::vector<int> a = {2, 1, 5, 1, 3, 2};
    int k = 3;
    std::cout << "max sum window size " << k << " = "
              << max_sum_k(a, k) << '\n';
    return 0;
}

Output yang Dihasilkan:

text

max sum window size 3 = 9

Baris for (int i = 0; i < k; ++i) current += a[i];: hitung jumlah window pertama a[0..k-1]. Kompleksitas O(k).
Baris current += a[i] - a[i - k];: geser window satu posisi. a[i] adalah elemen yang masuk (kanan), a[i-k] adalah elemen yang keluar (kiri). Ekspresi a[i] - a[i-k] adalah perubahan jumlah — efisien, hanya dua operasi.
Baris best = std::max(best, current);: update jawaban setiap iterasi. Kompleksitas total O(n).
Hasil 9: subarray {5, 1, 3} (indeks 2..4) berjumlah 9. Verifikasi: max dari {2+1+5=8, 1+5+1=7, 5+1+3=9, 1+3+2=6} = 9. Sesuai.

Variable-Size Window: Longest Substring Without Repeating Characters #

Aturan #

Diberikan string s, cari panjang substring terpanjang yang tidak memuat karakter berulang. Window membesar bila karakter baru unik; mengecil bila ada duplikat.

Mekanisme: Dua Pointer dengan Hash Set #

Variable-size window menggunakan dua pointer left dan right. right memperluas window dengan menambah karakter baru. Bila karakter sudah ada di window, left mengecilkan window hingga tidak ada duplikat.

flowchart TD Start["left=0, right=0, set={}"] --> Expand["right++: tambah s[right] ke set"] Expand --> Dup{duplikat?} Dup -- Ya --> Shrink["left++: hapus s[left] dari set"] Shrink --> Dup Dup -- Tidak --> Update["best = max(best, right-left+1)"] Update --> Expand

Kode: Variable-Size Window #

cpp
#include <iostream>
#include <string>
#include <unordered_set>
#include <algorithm>

int longest_unique(const std::string& s) {
    std::unordered_set<char> seen;
    int best = 0;
    int left = 0;
    for (int right = 0; right < static_cast<int>(s.size()); ++right) {
        while (seen.count(s[right])) {
            seen.erase(s[left]);
            ++left;
        }
        seen.insert(s[right]);
        best = std::max(best, right - left + 1);
    }
    return best;
}

int main() {
    std::string s = "abcabcbb";
    std::cout << "longest unique substring in \""
              << s << "\" = " << longest_unique(s) << '\n';

    s = "pwwkew";
    std::cout << "longest unique substring in \""
              << s << "\" = " << longest_unique(s) << '\n';

    s = "bbbb";
    std::cout << "longest unique substring in \""
              << s << "\" = " << longest_unique(s) << '\n';
    return 0;
}

Output yang Dihasilkan:

text
longest unique substring in "abcabcbb" = 3
longest unique substring in "pwwkew" = 3
longest unique substring in "bbbb" = 1

Baris for (int right = 0; right < s.size(); ++right): loop utama — right selalu maju. Total iterasi n.
Baris while (seen.count(s[right])): bila karakter s[right] sudah ada di window, kurangi window dari kiri hingga duplikat hilang. Loop while ini total berjalan paling banyak n kali seluruh program — sehingga total kompleksitas O(n).
Baris seen.insert(s[right]);: setelah window valid, tambahkan karakter baru ke set.
Baris best = std::max(best, right - left + 1);: window saat ini adalah s[left..right]. Panjangnya right - left + 1.
Hasil "abcabcbb" = 3: substring "abc" (atau "bca", "cab") — panjang 3. Sesuai.

Minimum Window Substring (Variasi Lanjutan) #

Aturan #

Diberikan string s dan string t, cari substring terpendek di s yang memuat seluruh karakter t (termasuk duplikatnya). Bila tidak ada, kembalikan string kosong.

Kode: Sliding Window dengan Counter #

cpp
#include <iostream>
#include <string>
#include <unordered_map>
#include <climits>

std::string min_window(const std::string& s, const std::string& t) {
    std::unordered_map<char, int> need, have;
    for (char c : t) need[c]++;

    int required = static_cast<int>(need.size());
    int formed = 0;
    int left = 0;
    int best_len = INT_MAX;
    int best_start = 0;

    for (int right = 0; right < static_cast<int>(s.size()); ++right) {
        char c = s[right];
        have[c]++;
        if (need.count(c) && have[c] == need[c]) formed++;

        while (formed == required && left <= right) {
            if (right - left + 1 < best_len) {
                best_len = right - left + 1;
                best_start = left;
            }
            char d = s[left];
            have[d]--;
            if (need.count(d) && have[d] < need[d]) formed--;
            ++left;
        }
    }
    return best_len == INT_MAX ? "" : s.substr(best_start, best_len);
}

int main() {
    std::cout << "min_window(\"ADOBECODEBANC\", \"ABC\") = \""
              << min_window("ADOBECODEBANC", "ABC") << "\"\n";
    std::cout << "min_window(\"a\", \"a\") = \""
              << min_window("a", "a") << "\"\n";
    std::cout << "min_window(\"a\", \"aa\") = \""
              << min_window("a", "aa") << "\"\n";
    return 0;
}

Output yang Dihasilkan:

text
min_window("ADOBECODEBANC", "ABC") = "BANC"
min_window("a", "a") = "a"
min_window("a", "aa") = ""

Baris for (char c : t) need[c]++;: hitung frekuensi karakter yang dibutuhkan dari t. Menjadi target window.
Baris if (need.count(c) && have[c] == need[c]) formed++;: bila karakter baru membuat jumlahnya tepat sama dengan kebutuhan, formed bertambah — satu karakter “lengkap”.
Loop while (formed == required): bila semua karakter t terpenuhi, coba mengecilkan window dari kiri untuk mencari window lebih pendek yang masih valid.
Baris if (need.count(d) && have[d] < need[d]) formed--;: bila pengurangan membuat jumlah di bawah kebutuhan, formed berkurang — window tidak lagi valid, keluar dari while.
Hasil "BANC": substring terpendek yang memuat A, B, C. Sesuai.

Pola Umum Sliding Window #

Berikut template umum yang dapat diterapkan ke banyak soal:

Jenis Soal	Window	Kondisi Expand	Kondisi Shrink
Max sum subarray size k	Fixed	Setelah k elemen pertama	Selalu (ukuran tetap k)
Longest unique substring	Variable	Tambah karakter kanan	Saat ada duplikat
Min window substring	Variable	Tambah karakter kanan	Saat semua target terpenuhi
Longest subarray sum ≤ K	Variable	Tambah elemen kanan	Saat sum > K
Permutation in string	Fixed	Setelah k elemen pertama	Selalu (ukuran tetap)

Ringkasan #

Sliding window memanfaatkan overlap antar window berturut-turut untuk menghindari recomputasi O(n²) → O(n).
Fixed-size window: hitung window awal O(k), lalu geser O(1) per langkah — total O(n).
Variable-size window: dua pointer left dan right. Loop utama right maju; while mengecilkan left bila kondisi dilanggar.
Analisis amortized O(n): meski ada nested loop, setiap elemen diproses paling banyak 2 kali (masuk dan keluar window).
Sliding window adalah solusi kanonik untuk soal subarray/substring optimal — kuasai pola umumnya untuk berbagai variasi.