DEV Community

Cover image for ✍Beginner-Friendly Guide 'Check If a String Contains All Binary Codes of Size K' - Problem 1461 (C++, Python, JavaScript)
Om Shree
Om Shree

Posted on

✍Beginner-Friendly Guide 'Check If a String Contains All Binary Codes of Size K' - Problem 1461 (C++, Python, JavaScript)

#programming #cpp #javascript #python

Binary strings are the DNA of computing, representing everything from simple numbers to complex encrypted files. This problem challenges you to determine if a long sequence of data contains every possible "word" of a specific length, a task that mirrors how scanners detect patterns or corruption in digital streams.

Problem Summary

You're given:

  • A binary string s consisting of only '0's and '1's.
  • An integer k representing the required length of each binary substring.

Your goal:

  • Return true if every possible binary code of length k exists as a substring within s. Otherwise, return false.

Intuition

To solve this efficiently, we first need to know how many unique binary codes exist for a given length . Since each position can be either a 0 or a 1, there are total unique combinations.

Instead of searching for every possible code one by one, we use a Sliding Window approach combined with a Hash Set or a boolean array. We slide a window of size across the string s, convert that window into a number, and mark that number as "seen." If by the end of the string we have seen unique numbers, we know every code is present.

To keep the performance high, we use bit manipulation. As the window moves one step to the right, we shift the previous value left, add the new bit, and use a "mask" to remove the bit that just fell out of the window.

Walkthrough: Understanding the Examples

Example 1: s = "00110110", k = 2

  • Possible codes for are: "00", "01", "10", "11". There are total codes.
  • Window 1: "00" (Seen: 00)
  • Window 2: "01" (Seen: 00, 01)
  • Window 3: "11" (Seen: 00, 01, 11)
  • Window 4: "10" (Seen: 00, 01, 11, 10)
  • All 4 unique codes are found. Result: true.

Example 3: s = "0110", k = 2

  • Possible codes for are: "00", "01", "10", "11".
  • Substrings in s: "01", "11", "10".
  • The code "00" is missing. Result: false.

C++ Solution 

class Solution {
 public:
  bool hasAllCodes(string s, int k) {
    int total_required = 1 << k;
    if (s.length() < k) return false;

    // used[i] tracks if we have encountered binary code i
    vector<bool> used(total_required, false);
    int count = 0;
    int window = 0;
    int mask = total_required - 1;

    for (int i = 0; i < s.length(); ++i) {
      // Shift left and add new bit
      window = ((window << 1) & mask) | (s[i] - '0');

      // Only start marking once we have at least k bits
      if (i >= k - 1) {
        if (!used[window]) {
          used[window] = true;
          count++;
        }
      }
    }

    return count == total_required;
  }
};
Enter fullscreen mode Exit fullscreen mode

Python Solution 

class Solution:
    def hasAllCodes(self, s: str, k: int) -> bool:
        total_required = 1 << k
        # Using a set is the most idiomatic Python way to track uniqueness
        seen = set()

        for i in range(len(s) - k + 1):
            # Extract the substring of length k
            substring = s[i : i + k]
            seen.add(substring)

            # Optimization: If we found everything, stop early
            if len(seen) == total_required:
                return True

        return len(seen) == total_required
Enter fullscreen mode Exit fullscreen mode

JavaScript Solution 

/**
 * @param {string} s
 * @param {number} k
 * @return {boolean}
 */
var hasAllCodes = function(s, k) {
    const totalRequired = 1 << k;
    const seen = new Set();

    for (let i = 0; i <= s.length - k; i++) {
        // Get the substring window
        const sub = s.substring(i, i + k);
        seen.add(sub);

        // Early exit if all codes are found
        if (seen.size === totalRequired) {
            return true;
        }
    }

    return seen.size === totalRequired;
};
Enter fullscreen mode Exit fullscreen mode

Key Takeaways

  • Bit Manipulation: Using 1 << k is an efficient way to calculate .
  • Sliding Window: This technique avoids redundant calculations by processing only the entering and exiting characters of a fixed length range.
  • Set Theory: Using a Hash Set (or boolean array) allows for time complexity when checking if a specific pattern has been encountered before.

Final Thoughts

This problem is a fantastic introduction to how stream processing works. In real world software engineering, similar logic is used in Bloom Filters or rolling hashes to detect duplicate data or identify specific signatures within massive datasets, such as network packets or genomic sequences. Mastering the sliding window will serve you well in technical interviews, as it often turns problems into solutions.

Top comments (0)