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

solution.cpp

class Solution {
public:
    bool hasAllCodes(string s, int k) {
        if (k > s.size()) return false;
        int x = 0;
        for (int i = 0; i < k; ++i) {
            x <<= 1;
            x += (s[i] == '1');
        }
        bool a[1<<k];
        memset(a, 0, sizeof a);
        a[x] = true;
        for (int i = k; i < s.size(); ++i) {
            x <<= 1;
            if (x >= (1 << k)) x -= (1 << k);
            x += (s[i] == '1');
            a[x] = true;
        }
        for (int j = 0; j < (1 << k); ++j)
            if (a[j] == false) return false;
        return true;
    }
};

solution.md

This is a tutorial to solve the problem LeetCode#1461

Algorithm

Two cases

• The length of string s is smaller than k: We cannot find any binary string of length k that is a substring of s, the function simply returns false.
• The length of string s is greater than or equal to k: We will attempt to check all substrings of length k in s. For each binary substring, we derive a corresponding decimal value x. Then we mark the x-th element of a boolean array a as true. After going through all elements, we check if the whole array is marked true. If it is, the function returns true; otherwise, returns false.

How do we check all substrings?

First, you consider the substring s[0..k-1] of s (i.e. the k-prefix of s). You can calculate the corresponding x value very easily:

1. At first, x is zero.
2. For every character read from the string:
   1. shift left x by 1 bit (i.e. x = x*2).
   2. add 1 to x if the character is '1'
3. Mark a[x] true

For example your substring is 110. At first x is zero. You read the substring from left to right:

• '1': x <<= 1 (x is still 0), then x += 1 (x becomes 1)
• '1': x <<= 1 (x becomes 2), then x += 1 (x becomes 3)
• '0': x <<= 1 (x becomes 6), then x += 0 (x is still 6)

In the end, we have x equal 6, which is exactly the decimal value of the binary string 110

Do that for the first k characters and we will obtain the value x for the first substring.

For the next substrings (i.e. s[1..k], s[2..k+1], etc.), the idea is a little bit different, but quite similar.

1. Keep x as the decimal value of s[0..k-1]
2. For each character read from the string:
   1. shift left x by 1 bit (i.e. x = x*2)
   2. if x is greater than or equal to 1 << k, make x -= (1 << k)
   3. add 1 to x if the character is '1'
   4. mark a[x] true

Notice that we have an extra step. If x is greater than or equal to 1 << k (this C++ notation means ), that means x has used more than k bits, we need to substract x by 1 << k to keep x only using k bits. For example we have k equal 3, thus any number larger than or equal to uses more than 3 bits. (8 is 1000, 9 is 1001, 12 is 1100, etc.)

It is also important to note that, substracting a random number by 1 << k does not guarantee to make that number using at most k bits. However, as we started with x less than 1 << k, and every time the number of bits that x uses exceeds k, substracting will make sure x using at most k bits. There will not be a point in our algorithm where x uses k+2 bits.

Does step 2.3 will make x longer than k bits?

After step 2.1, x is even. After step 2.2, if x is changed, it is subtracted by 1 << k, which is itself an even number. Thus at step 2.3, x is even. Adding 1 to x will not make it using more bits.

Analysis

For the solution described above:

• The space complexity is (mainly because we need an array to mark which x value showed up)
• The time complexity is (iterate over the string)

Note that bit-shifting operator (e.g. x << 1) is faster than normal multiplication (e.g. x * 2). The attached C++ code above has remarkable performance:

• Runtime: 144 ms, faster than 98.81% of C++ online submissions for Check If a String Contains All Binary Codes of Size K.
• Memory Usage: 17.8 MB, less than 97.21% of C++ online submissions for Check If a String Contains All Binary Codes of Size K.