1461. Check If a String Contains All Binary Codes of Size K

/**
 * Problem: LeetCode 1461 - Check If a String Contains All Binary Codes of Size K
 * Difficulty: Medium
 * Language: Java
 * Author: CodeByTushu
 */
class Solution {
    public boolean hasAllCodes(String s, int k) {
        int target = 1 << k;
        if (s.length() - k + 1 < target) {
            return false;
        }

        boolean[] seen = new boolean[target];
        int count = 0;
        int hash = 0;
        int mask = target - 1;

        for (int i = 0; i < s.length(); i++) {
            hash = ((hash << 1) & mask) | (s.charAt(i) - '0');
            if (i >= k - 1) {
                if (!seen[hash]) {
                    seen[hash] = true;
                    count++;
                    if (count == target) {
                        return true;
                    }
                }
            }
        }

        return count == target;
    }
}

"""
Problem: LeetCode 1461 - Check If a String Contains All Binary Codes of Size K
Difficulty: Medium
Language: Python
Author: CodeByTushu
"""
class Solution:
    def hasAllCodes(self, s: str, k: int) -> bool:
        target = 1 << k
        if len(s) - k + 1 < target:
            return False

        seen = bytearray(target)
        count = 0
        hash_val = 0
        mask = target - 1

        for i, ch in enumerate(s):
            hash_val = ((hash_val << 1) & mask) | (ord(ch) - 48)
            if i >= k - 1:
                if not seen[hash_val]:
                    seen[hash_val] = 1
                    count += 1
                    if count == target:
                        return True

        return count == target

/**
 * Problem: LeetCode 1461 - Check If a String Contains All Binary Codes of Size K
 * Difficulty: Medium
 * Language: C++
 * Author: CodeByTushu
 */
#include <string>
#include <vector>

using namespace std;

class Solution {
public:
    bool hasAllCodes(string s, int k) {
        int target = 1 << k;
        if ((int)s.length() - k + 1 < target) {
            return false;
        }

        vector<bool> seen(target, false);
        int count = 0;
        int hashVal = 0;
        int mask = target - 1;

        for (int i = 0; i < (int)s.length(); i++) {
            hashVal = ((hashVal << 1) & mask) | (s[i] - '0');
            if (i >= k - 1) {
                if (!seen[hashVal]) {
                    seen[hashVal] = true;
                    count++;
                    if (count == target) {
                        return true;
                    }
                }
            }
        }

        return count == target;
    }
};

/**
 * Problem: LeetCode 1461 - Check If a String Contains All Binary Codes of Size K
 * Difficulty: Medium
 * Language: JavaScript
 * Author: CodeByTushu
 */
/**
 * @param {string} s
 * @param {number} k
 * @return {boolean}
 */
var hasAllCodes = function(s, k) {
    const target = 1 << k;
    if (s.length - k + 1 < target) {
        return false;
    }

    const seen = new Uint8Array(target);
    let count = 0;
    let hashVal = 0;
    const mask = target - 1;

    for (let i = 0; i < s.length; i++) {
        hashVal = ((hashVal << 1) & mask) | (s.charCodeAt(i) - 48);
        if (i >= k - 1) {
            if (seen[hashVal] === 0) {
                seen[hashVal] = 1;
                count++;
                if (count === target) {
                    return true;
                }
            }
        }
    }

    return count === target;
};