Sliding Window

Sliding window sudah kita pelajari di Chapter Sliding Window di Section Array dengan contoh fixed-size dan variable-size (longest unique substring, min window substring). Pada Chapter ini kita akan melihat variasi lanjutan yang sering muncul di kompetisi: longest subarray with at most K distinct (window variabel + hash map counter), longest subarray with sum at most K (window variabel + asumsi non-negatif), dan permutation in string (fixed window + counter). Tujuan kita adalah menguasai pola umum sehingga dapat dikenali pada soal baru.

Recap: Pola Umum Sliding Window #

Variasi 1: Longest Subarray dengan At Most K Distinct #

Aturan #

Diberikan array a dan integer K, cari panjang subarray terpanjang yang memuat paling banyak K elemen berbeda. Bila K = 0, jawaban 0.

Mekanisme: Counter Hash Map #

Gunakan unordered_map<int,int> count untuk melacak frekuensi elemen di window. Saat count.size() > K, mengecilkan window dari kiri sampai kembali ≤ K.

Kode: K-Distinct Window #

#include <iostream>
#include <vector>
#include <unordered_map>
#include <algorithm>

int longest_k_distinct(const std::vector<int>& a, int K) {
    if (K == 0) return 0;
    std::unordered_map<int,int> count;
    int best = 0;
    int left = 0;
    for (int right = 0; right < static_cast<int>(a.size()); ++right) {
        count[a[right]]++;
        while (static_cast<int>(count.size()) > K) {
            if (--count[a[left]] == 0) count.erase(a[left]);
            ++left;
        }
        best = std::max(best, right - left + 1);
    }
    return best;
}

int main() {
    std::vector<int> a = {1, 2, 1, 2, 3, 3, 4, 2, 1};
    for (int K : {0, 1, 2, 3}) {
        std::cout << "K=" << K << " -> longest = "
                  << longest_k_distinct(a, K) << '\n';
    }
    return 0;
}

Output yang Dihasilkan:

K=0 -> longest = 0
K=1 -> longest = 2
K=2 -> longest = 4
K=3 -> longest = 6

1. Baris std::unordered_map<int,int> count;: melacak frekuensi setiap nilai di window. count.size() = jumlah elemen unik.
2. Baris count[a[right]]++;: tambahkan elemen yang masuk. Bila baru, count.size() bertambah.
3. Baris while (count.size() > K): selama distinct melebihi K, mengecilkan window dari kiri.
4. Baris if (--count[a[left]] == 0) count.erase(a[left]);: kurangi frekuensi elemen yang keluar. Bila frekuensi mencapai 0, hapus dari map agar count.size() akurat.
5. Baris ++left;: majukan pointer kiri.
6. Baris best = std::max(best, right - left + 1);: window saat ini valid (≤ K distinct), update jawaban.
7. Hasil K=2 -> 4: subarray {1, 2, 1, 2} memiliki distinct = {1, 2} → panjang 4.
8. Hasil K=3 -> 6: subarray {1, 2, 1, 2, 3, 3} memiliki distinct = {1, 2, 3} → panjang 6.

Variasi 2: Longest Subarray dengan Sum ≤ K #

Aturan #

Diberikan array a berisi non-negatif dan integer K, cari panjang subarray terpanjang dengan jumlah elemen ≤ K. Bila semua elemen positif, sliding window langsung bekerja. Bila ada elemen negatif, sliding window tidak valid — gunakan prefix sum + binary search.

Kode: Sum ≤ K (Semua Non-Negatif) #

#include <iostream>
#include <vector>
#include <algorithm>

int longest_sum_le(const std::vector<int>& a, long long K) {
    int best = 0;
    long long cur = 0;
    int left = 0;
    for (int right = 0; right < static_cast<int>(a.size()); ++right) {
        cur += a[right];
        while (cur > K && left <= right) {
            cur -= a[left];
            ++left;
        }
        best = std::max(best, right - left + 1);
    }
    return best;
}

int main() {
    std::vector<int> a = {2, 3, 1, 2, 4, 3};
    for (int K : {4, 7, 10, 100}) {
        std::cout << "K=" << K << " -> longest = "
                  << longest_sum_le(a, K) << '\n';
    }
    return 0;
}

Output yang Dihasilkan:

K=4 -> longest = 2
K=7 -> longest = 3
K=10 -> longest = 4
K=100 -> longest = 6

1. Baris cur += a[right];: tambahkan elemen baru ke jumlah window.
2. Baris while (cur > K && left <= right): selama jumlah melebihi K, keluarkan elemen kiri. Asumsi non-negatif penting di sini — bila ada negatif, cur bisa tidak monoton saat right maju, sehingga strategi ini gagal.
3. Baris cur -= a[left]; ++left;: kurangi jumlah, majukan kiri.
4. Baris best = std::max(best, right - left + 1);: window saat ini valid (sum ≤ K), update.
5. Hasil K=4 -> 2: subarray {3, 1} sum = 4 (panjang 2).
6. Hasil K=10 -> 4: subarray {3, 1, 2, 4} sum = 10 (panjang 4).

Variasi 3: Permutation in String #

Aturan #

Diberikan string s1 (pola) dan string s2 (teks). Cari apakah ada permutasi s1 yang muncul sebagai substring di s2. Karena panjang pola tetap |s1|, ini adalah fixed-window dengan counter.

Mekanisme: Counter Match #

Pertahankan window berukuran |s1| di s2. Hitung frekuensi karakter di window dan bandingkan dengan frekuensi s1. Untuk efisiensi, lacak jumlah karakter yang frekuensinya cocok (matched). Saat semua cocok, window adalah permutasi s1.

Kode: Permutation Check #

#include <iostream>
#include <string>
#include <array>

bool check_inclusion(const std::string& s1, const std::string& s2) {
    if (s1.size() > s2.size()) return false;
    std::array<int, 26> target{}, window{};
    for (char c : s1) target[c - 'a']++;
    for (size_t i = 0; i < s1.size(); ++i) window[s2[i] - 'a']++;

    int matched = 0;
    for (int i = 0; i < 26; ++i) if (target[i] == window[i]) matched++;
    if (matched == 26) return true;

    for (size_t i = s1.size(); i < s2.size(); ++i) {
        char out_char = s2[i - s1.size()];
        char in_char  = s2[i];
        // Karakter keluar
        if (window[out_char - 'a'] == target[out_char - 'a']) matched--;
        window[out_char - 'a']--;
        if (window[out_char - 'a'] == target[out_char - 'a']) matched++;
        // Karakter masuk
        if (window[in_char - 'a'] == target[in_char - 'a']) matched--;
        window[in_char - 'a']++;
        if (window[in_char - 'a'] == target[in_char - 'a']) matched++;
        if (matched == 26) return true;
    }
    return false;
}

int main() {
    std::cout << std::boolalpha;
    std::cout << "check_inclusion(\"ab\", \"eidbaooo\") = "
              << check_inclusion("ab", "eidbaooo") << '\n';
    std::cout << "check_inclusion(\"ab\", \"eidboaoo\") = "
              << check_inclusion("ab", "eidboaoo") << '\n';
    std::cout << "check_inclusion(\"adc\", \"dcda\") = "
              << check_inclusion("adc", "dcda") << '\n';
    return 0;
}

Output yang Dihasilkan:

check_inclusion("ab", "eidbaooo") = true
check_inclusion("ab", "eidboaoo") = false
check_inclusion("adc", "dcda") = true

1. Baris std::array<int, 26> target{}, window{};: dua counter frekuensi untuk 26 huruf kecil. Inisialisasi value-initialize ke 0.
2. Baris for (char c : s1) target[c - 'a']++;: hitung frekuensi pola s1.
3. Baris for (size_t i = 0; i < s1.size(); ++i) window[s2[i] - 'a']++;: isi window awal dari s2[0..|s1|-1].
4. Baris for (int i = 0; i < 26; ++i) if (target[i] == window[i]) matched++;: hitung berapa huruf yang frekuensinya sudah cocok antara window dan target. Maksimal 26.
5. Baris if (matched == 26) return true;: bila semua 26 huruf cocok, window adalah permutasi s1.
6. Block karakter keluar: bila sebelum perubahan window cocok dengan target, kurangi matched. Setelah update, bila kembali cocok, tambah matched. Dua cek agar transisi tepat.
7. Block karakter masuk: simetri — cek sebelum dan sesudah update window.
8. Hasil ("ab", "eidbaooo") = true: substring "ba" di indeks 3..4 adalah permutasi "ab". Sesuai.

Ringkasan #

• Sliding window variable selalu punya pola: right maju di luar, left maju di while dalam. O(n) amortized.
• K-distinct: hash map counter + erase saat frekuensi 0. Kompleksitas O(n) rata-rata.
• Sum ≤ K (asumsi non-negatif): akumulasi cur, shrink dari kiri saat cur > K. Bila ada negatif, ganti ke prefix sum + struktur data.
• Permutation in string: fixed window dengan counter matched agar update O(1) per geseran.
• Pola umum: pilih fixed bila ukuran diketahui, variable bila kondisi berupa batas (≤, ≥, distinct count).