Check If a String Contains All Binary Codes of Size K

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.

A binary code of length k is a string of exactly k characters, where each character is either '0' or '1'.

Note: There are exactly 2^k different binary codes of length k. For example, when k=2, the binary codes are "00", "01", "10", and "11".

Input & Output

Example 1 — All Codes Present

$ Input: s = "00110110", k = 2

› Output: true

💡 Note: For k=2, we need all 4 binary codes: "00", "01", "10", "11". String contains: "00" at index 0, "01" at index 1, "11" at index 2-3, "10" at index 4-5. All codes are present.

Example 2 — Missing Code

$ Input: s = "0110", k = 1

› Output: true

💡 Note: For k=1, we need codes "0" and "1". String "0110" contains both: "0" at index 0 and "1" at indices 1,2. All codes present.

Example 3 — String Too Short

$ Input: s = "0110", k = 2

› Output: false

💡 Note: For k=2, we need 4 codes: "00", "01", "10", "11". String contains "01" at index 0, "11" at index 1, "10" at index 2. Missing "00", so return false.

Constraints

1 ≤ s.length ≤ 5 × 10⁴
1 ≤ k ≤ 20
s consists of only '0' and '1' characters

Visualization

Tap to expand

Understanding the Visualization

Input

Binary string s and integer k

Process

Extract all k-length substrings and count unique ones

Output

Return true if count equals 2^k

Key Takeaway

🎯 Key Insight: Use rolling hash to convert k-length binary substrings to integers for O(1) processing

Asked in

F Facebook 35 G Google 28 a Amazon 22

The key insight is that we need exactly 2^k different binary codes of length k. The optimal approach uses rolling hash to efficiently convert binary substrings to integers, avoiding string operations. Best approach is rolling hash with early termination. Time: O(n), Space: O(2^k)

Common Approaches

Approach	Time	Space	Notes
✓ Rolling Hash with Early Termination	O(n)	O(2^k)	Use rolling hash to efficiently track k-length substrings with early exit
Sliding Window with Hash Set	O(n × k)	O(2^k × k)	Use sliding window to collect all k-length substrings, check if count equals 2^k
Generate All Codes and Search	O(2^k × n × k)	O(2^k × k)	Generate all 2^k binary codes and check if each exists as substring

Rolling Hash with Early Termination — Algorithm Steps

Convert initial k characters to integer
Roll the hash: remove leftmost bit, add rightmost bit
Add each hash to set and check if we have all 2^k codes
Return true immediately when target reached

Visualization

Tap to expand

Step-by-Step Walkthrough

Initial Hash

Convert first k bits to integer

Roll Hash

Shift left, mask, add new bit

Early Exit

Stop when all 2^k codes found

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>
#include <math.h>

#define MAX_CODES 100000

bool solution(char* s, int k) {
    int len = strlen(s);
    if (len < k) return false;
    
    int targetCount = (int)pow(2, k);
    if (len < targetCount + k - 1) return false;
    
    int hashes[MAX_CODES];
    int hashCount = 0;
    int hashVal = 0;
    
    // Build initial hash for first k characters
    for (int i = 0; i < k; i++) {
        hashVal = (hashVal << 1) + (s[i] - '0');
    }
    hashes[hashCount++] = hashVal;
    
    // Rolling hash for remaining positions
    int mask = (1 << k) - 1; // k bits of 1s
    
    for (int i = k; i < len; i++) {
        // Remove leftmost bit and add rightmost bit
        hashVal = ((hashVal << 1) & mask) + (s[i] - '0');
        
        // Check if already seen
        bool found = false;
        for (int j = 0; j < hashCount; j++) {
            if (hashes[j] == hashVal) {
                found = true;
                break;
            }
        }
        
        if (!found && hashCount < MAX_CODES) {
            hashes[hashCount++] = hashVal;
            
            // Early termination
            if (hashCount == targetCount) {
                return true;
            }
        }
    }
    
    return hashCount == targetCount;
}

int main() {
    char s[100001];
    fgets(s, sizeof(s), stdin);
    s[strcspn(s, "\n")] = 0;
    
    int k;
    scanf("%d", &k);
    
    bool result = solution(s, k);
    printf(result ? "true\n" : "false\n");
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Single pass through string with O(1) hash operations

✓ Linear Growth

Space Complexity

O(2^k)

Hash set stores at most 2^k integer hashes

✓ Linear Space

28.5K Views

Medium Frequency

~25 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Rolling Hash with Early Termination — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler