Kiểm tra chuỗi chứa tất cả mã nhị phân độ dài K (Check If a String Contains All Binary Codes of Size K) trong C++

Cho chuỗi nhị phân s và số nguyên k. Kiểm tra xem mọi mã nhị phân độ dài k (tổng cộng 2^k mã) có xuất hiện dưới dạng chuỗi con của s hay không.

Ví dụ

Đầu vào: s = "00110110", k = 2
Đầu ra: true (các mã "00","01","10","11" đều có mặt).

Thuật toán cửa sổ trượt + Hash Set

1. Duy trì cửa sổ độ dài k trượt qua s.
2. Dùng unordered_set<string> (hoặc bitset/mảng bool nếu k ≤ 20) lưu các mã đã thấy.
3. Nếu kích thước set đạt 2^k → trả về true sớm.
4. Kết thúc duyệt → trả về false.

Triển khai C++ (tối ưu với bitmask)

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    bool hasAllCodes(string s, int k) {
        if (s.size() < k) return false;
        int need = 1 << k;
        vector<bool> seen(need, false);
        int mask = need - 1;
        int val = 0;
        for (int i = 0; i < s.size(); ++i) {
            val = ((val << 1) & mask) | (s[i] - '0');
            if (i >= k - 1) {
                if (!seen[val]) {
                    seen[val] = true;
                    if (--need == 0) return true;
                }
            }
        }
        return false;
    }
};

Độ phức tạp

• Thời gian: O(N) - duyệt chuỗi một lần.
• Không gian: O(2^k) - mảng đánh dấu (k ≤ 20 theo constraints).

Kết quả kiểm thử

Đầu vào: "00110110", 2
Đầu ra: 1 (true)