ตรวจสอบสตริงไบนารีครบทุกการจัดเรียงความยาว k ใน C++

ปัญหา

ให้สตริงไบนารี (ประกอบ 0, 1) และจำนวนเต็ม k ตรวจสอบว่าสตริงนี้มี substring ครบทุกการจัดเรียง (permutation) ของ k บิตไบนารีหรือไม่

จำนวน permutation ทั้งหมด = 2^k

ตัวอย่าง: str = "11001", k = 2

Permutations ของ 2 บิต: 00, 01, 10, 11

Substrings ความยาว 2 ใน "11001": 11, 10, 00, 01 → ครบทุกตัว ✓

อัลกอริทึม

1. สร้างทุก permutation ของ k บิต (2^k ตัว)
2. ตรวจสอบแต่ละ permutation ว่ามีเป็น substring ใน str หรือไม่
3. ถ้าครบทุกตัว → true, ไม่เช่นนั้น → false

ตัวอย่างโค้ด C++

#include <iostream>
#include <vector>
#include <string>
#include <cmath>
using namespace std;

vector generateBinaryPermutations(int k) {
    vector perms;
    int total = 1 << k; // 2^k
    
    for (int i = 0; i < total; i++) {
        string s(k, '0');
        for (int j = 0; j < k; j++) {
            if (i & (1 << (k - 1 - j))) // MSB first
                s[j] = '1';
        }
        perms.push_back(s);
    }
    return perms;
}

bool hasAllPermutations(const string& str, int k) {
    vector perms = generateBinaryPermutations(k);
    
    for (const string& p : perms) {
        if (str.find(p) == string::npos)
            return false;
    }
    return true;
}

int main() {
    string str = "11001";
    int k = 2;
    
    cout << "String: " << str << ", k = " << k << endl;
    cout << "All " << (1<

ผลลัพธ์
String: 11001, k = 2
All 4 permutations: 00 01 10 11
Has ALL permutations

Test k=3, str=1101001: YES

การปรับปรุงประสิทธิภาพ (สำคัญ!)
วิธีข้างต้น O(2^k × n) ช้ามากสำหรับ k ใหญ่
วิธีที่ดีกว่า: Sliding Window + Bitmask
bool hasAllPermutationsFast(const string& str, int k) {
    if (str.length() < k) return false;
    int total = 1 << k;
    vector seen(total, false);
    int count = 0;
    
    // เริ่มต้น window แรก
    int mask = 0;
    for (int i = 0; i < k; i++)
        mask = (mask << 1) | (str[i] - '0');
    seen[mask] = true;
    count++;
    
    // Slide window
    int windowMask = (1 << k) - 1; // k lower bits
    for (int i = k; i < str.length(); i++) {
        mask = ((mask << 1) & windowMask) | (str[i] - '0');
        if (!seen[mask]) {
            seen[mask] = true;
            if (++count == total) return true;
        }
    }
    return count == total;
}
ความซับซ้อน: O(n + 2^k) เวลา, O(2^k) พื้นที่ - เร็วมาก!

De Bruijn Sequence
สตริงที่มีความยาวน้อยที่สุดที่ครบทุก k-permutation คือ De Bruijn sequence ความยาว = 2^k + k - 1
ตัวอย่าง k=2: "00110" (ความยาว 5) ครบ 00,01,11,10