[LeetCode] Check If a String Contains All Binary Codes of Size K

Problem: 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.

Example:

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 indicies 0, 1, 3 and 2 respectively.

Input: s = "00110", k = 2
Output: true

Input: s = "0110", k = 1
Output: true
Explanation: The binary codes of length 1 are "0" and "1", it is clear that both exist as a substring. 

Input: s = "0110", k = 2
Output: false
Explanation: The binary code "00" is of length 2 and doesn't exist in the array.

Input: s = "0000000001011100", k = 4
Output: false

Approach: The intuition here is the number of k bit integers is 2^k. Now we just need to check if the number of unique substrings of size k in the given string is 2^k then we get all the binary codes otherwise if we didn't. Here is the algorithm look like:

• HashSet set = {}
• FOR i = 0 to n - k
• set.Add(s.Substring(i, k))
• RETURN Count(set) == 2 ^ k

The above approach will work correctly but it will be expensive as it will take O(n * k) time. Let's try to do better. The problem here getting substring itself take O(k) time. We can reduce this time. If you see it's kind of sliding window where at every step one character form start is getting removed from window and next character is getting added. 

We can basically calculate the decimal number formed by the first k binary characters and then we can use current decimal number to get the next decimal number. In the end if the number of unique formed decimal numbers is 2^k then we can return true otherwise false. Let's try to understand how to calculate the next decimal number given the current one using an example:

Say s = "00110" and k = 2

Max number formed by k (= 2) bits is (2^2 - 1 =) 3 (binary representation = 11). Let's call it maxKBitNumber.

First 2 binary characters will make the number 0 ("00"), call it currDecimalNumber.

Now the next character is '1'. Here is the formula which we can use: 

nextDecimalNumber = ((currDecimalNumber << 1) & maxKBitNumber) | (currChar - '0')

nextDecimalNumber  = ((0 << 1) & 3) | 1 = 1

Now next char is '1' and currDecimalNumber is also 1 so:

nextDecimalNumber  = ((1 << 1) & 3) | 1 = 3

Now the next char is '0' and currDecimalNumber is 3, so 

nextDecimalNumber  = ((3 << 1) & 3) | 0 = 2

Hopefully the approach is clear now.

Implementation in C#:

Approach 1: Using substrings:

    public bool HasAllCodes1(string s, int k) 

    {

        HashSet<string> binaryCodesSet = new HashSet<string>();    

        for (int i = 0; i + k <= s.Length; ++i)

        {

            binaryCodesSet.Add(s.Substring(i, k));

        }

        return (1 << k) == binaryCodesSet.Count;

    }

Approach 2: Using sliding window:

    public bool HasAllCodes(string s, int k) 

    {

        HashSet<int> decimalValsSet = new HashSet<int>();

        int numOfAllKBitIntegers = (1 << k);

        int maxKBitNum = numOfAllKBitIntegers - 1;

        int decimalVal = 0;

        // Getting the first k bit binary number

        for (int i = 0; i < k && i < s.Length; ++i)

        {

            decimalVal = ((decimalVal << 1) & maxKBitNum) | (s[i] - '0');

        }

        decimalValsSet.Add(decimalVal);

        for (int i = k; i < s.Length; ++i)

        {

            decimalVal = ((decimalVal << 1) & maxKBitNum) | (s[i] - '0');

            decimalValsSet.Add(decimalVal);

        }

        return numOfAllKBitIntegers == decimalValsSet.Count;

    }

Complexity: Approach 1: O(n *k), Approach 2: O(n)