Check if a String Contains all Binary Codes of Size K

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 1

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.

Example 2

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.

Example 3

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

Constraints:

1 <= s.length <= 5 * 10⁵
s[i] is either '0' or '1'.
1 <= k <= 20.

Solution 1 - Generate all possible K length substrings, store them in a HashSet, and check if it has K length binary strings

Solution 1 - Generate all possible K length substrings, store them in a HashSet, and check if it has K length binary strings

In this approach, we are going to generate all possible k length substrings and store them in a HashSet, while storing them into the set, check if it reaches size of k length binary strings which is 2^k. For example, if k is 2, then possible binary substrings are 00, 01, 10 and 11, so total number of combinations possible with k distinct 0's and 1's are 2^k.

Java

import java.util.HashSet;

public class CheckIfStringContainsAllBinaryCodesOfSizeK {

    static boolean hasAllCodes(String s, int k) {
        int expectedTotal  = 1 <<k; // equivalent to Math.pow(2, k)
        HashSet<String> uniqueBinaryCodes = new HashSet<>();
        for(int i=0; i<s.length()-(k-1); i++) {
            String kLengthBinary = s.substring(i, i+k);
            uniqueBinaryCodes.add(kLengthBinary);
            if(uniqueBinaryCodes.size() == expectedTotal){
                return true;
            }
        }
        return false;
    }

    public static void main(String[] args) {
        System.out.println(hasAllCodes("00110110", 2));
        System.out.println(hasAllCodes("00110", 2));
    }
}

Complexity Analysis:

Time complexity: Above code runs in O(n * k) time where n is the length of input string s.
Space complexity: O(n * k) , since we are storing n possible substrings and each of length k, we can also say this is 2^k as there will be these many binary substrings possible with k distinct 0's and 1's.

Above implementations source code can be found at GitHub link for Java code