Question Link

https://leetcode.com/problems/check-if-a-string-contains-all-binary-codes-of-size-k/

Question Description

Given a binary string s and an integer k, return true if every binary code of length k is a substring of s. Otherwise, return false.
Input: s = “00110110”, k = 2
Output: true
Explanation: The binary codes of length 2 are “00”, “01”, “10” and “11”. They can be all found as substrings at indices 0, 1, 3 and 2 respectively.

Simulation

Solution 1: SlideWindow + Hashset

Step 1: Define a hashset
Step 2: Traverse the string by adding all the elements into the set
Step 3: Check if the set equals the number of combination from k

Solution 2： SlideWindow + Hash-Like Array + Bit

Implementation

Solution 1: Sliding Window

    public boolean hasAllCodes(String s, int k) {
        Set <String> set = new HashSet < > ();
        if (s.length() - k < 0) return false;
        for (int i = 0; i <= s.length() - k; i++) 
            set.add(s.substring(i, i + k));
        return set.size() == Math.pow(2, k);
    }

Solution 2: Bit+Sliding Window

public boolean hasAllCodes(String s, int k) {
    if (s.length() < k) return false;
    boolean[] combination = new boolean[1 << k];
    int size = combination.length;
    int bit = 0;
    for (int i = 0; i < k; i++) {
        bit = bit << 1;
        bit = bit ^ (s.charAt(i) - '0');
    }
    combination[bit] = true;
    size--;
    for (int i = k; i < s.length(); i++) {
        bit = bit << 1;
        bit = bit & ~(1 << k);
        bit = bit ^ (s.charAt(i) - '0');
        if (combination[bit] == false) {
            combination[bit] = true;
            size--;
        }
        if (size == 0) {
            return true;
        }
    }
    return false;
}