Check If a String Contains All Binary Codes of Size K

class Solution {
    public static boolean containsAllKLengthSubstrings(String input, int k) {
        int required = 1 << k;
        boolean[] found = new boolean[required];
        int mask = required - 1;
        int hashValue = 0;

        for (int index = 0; index < input.length(); index++) {
            hashValue = ((hashValue << 1) & mask) | (input.charAt(index) - '0');
            if (index >= k - 1 && !found[hashValue]) {
                found[hashValue] = true;
                required--;
                if (required == 0) {
                    return true;
                }
            }
        }
        return false;
    }
}

This Java solution determines if a given string contains all possible substrings of binary codes of size k. To achieve this, follow the established methodologies:

• Calculate required, the total number of possible binary codes of size k, using bit shifting (1 << k).
• Utilize a boolean[] found to keep track of which binary codes have been found.
• Use mask (computed as required - 1) to restrict the hashValue to the last k bits.
• Iterate over each character of the input string, updating the hashValue by left shifting it, applying the mask, and adding the current binary value of the character.
• Check if the k-length substring represented by hashValue has not been found yet; if true, mark it as found and decrease required by 1.
• If required becomes 0, return true indicating all binary codes of length k are present in the string.
• If the loop completes without finding all codes, return false.

Ensure correct input parameters with the string being potentially very large and k being an appropriate integer. This method effectively tracks the occurrence of binary codes using a space-efficient approach.

class Solution:
    def containsAllBinaryCodes(self, sequence: str, length: int) -> bool:
        required = 1 << length
        seen = [False] * required
        full_mask = required - 1
        current_hash = 0

        for j in range(len(sequence)):
            # Calculate the bit hash for current window
            current_hash = ((current_hash << 1) & full_mask) | (int(sequence[j]))
            # Mark as seen if the current hash index marks first occurrence
            if j >= length - 1 and not seen[current_hash]:
                seen[current_hash] = True
                required -= 1
                if required == 0:
                    return True
        return False

The Python3 solution defines a method containsAllBinaryCodes, which checks if a string contains all possible binary codes of a given size k. The approach utilizes bit manipulation and a sliding window technique to efficiently solve the problem. Here’s a breakdown of the implementation:

• Initialize required to be (2^k) (number of unique binary codes of size k).
• Create a seen list of boolean values to track which binary codes are identified in the sequence.
• Calculate full_mask as (2^k - 1). This mask helps manage the hash to be within the scope of k-bits.
• Initialize current_hash to track the current bit pattern of the window of size k in the sequence.

For each character sequence[j]:

• The current_hash is updated using bit manipulation. Left shift to make room for the new bit and use the OR operation to add the current character as the least significant bit.
• The sliding window (denoted by current_hash) checks if the current bit pattern has been seen. If it's a fresh pattern and its index was not seen, the seen index is marked True and required is decremented.
• Reducing required each time a new code is encountered ensures that once it reaches zero, all possible codes of length k are found in the sequence.

Should all binary codes be encountered before the end of the string, the function returns True indicating the string contains all binary codes of size k. If the loop completes without finding all codes, it returns False.