1461. Check If a String Contains All Binary Codes of Size K LeetCode Solution

In this guide, you will get 1461. Check If a String Contains All Binary Codes of Size K LeetCode Solution with the best time and space complexity. The solution to Check If a String Contains All Binary Codes of Size K problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Check If a String Contains All Binary Codes of Size K solution in C++
Check If a String Contains All Binary Codes of Size K solution in Java
Check If a String Contains All Binary Codes of Size K solution in Python
Additional Resources

1461. Check If a String Contains All Binary Codes of Size K LeetCode Solution image

Problem Statement of 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 * 105
s[i] is either '0' or '1'.
1 <= k <= 20

Complexity Analysis

Time Complexity: O(|\texttt{s}|)
Space Complexity: O(|\texttt{s}|)

1461. Check If a String Contains All Binary Codes of Size K LeetCode Solution in C++

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

    // used[i] := true if i is a substring of `s`
    vector<bool> used(n);

    int window = k == 1 ? 0 : stoi(s.substr(0, k - 1), nullptr, 2);
    for (int i = k - 1; i < s.length(); ++i) {
      // Include the s[i].
      window = (window << 1) + (s[i] - '0');
      // Discard the s[i - k].
      window &= n - 1;
      used[window] = true;
    }

    return ranges::all_of(used, [](bool u) { return u; });
  }
};
/* code provided by PROGIEZ */

1461. Check If a String Contains All Binary Codes of Size K LeetCode Solution in Java

class Solution {
  public boolean hasAllCodes(String s, int k) {
    final int n = 1 << k;
    if (s.length() < n)
      return false;

    // used[i] := true if i is a substring of `s`
    boolean[] used = new boolean[n];

    int window = k == 1 ? 0 : Integer.parseInt(s.substring(0, k - 1), 2);
    for (int i = k - 1; i < s.length(); ++i) {
      // Include the s[i].
      window = (window << 1) + (s.charAt(i) - '0');
      // Discard the s[i - k].
      window &= n - 1;
      used[window] = true;
    }

    return IntStream.range(0, used.length).mapToObj(i -> used[i]).allMatch(u -> u);
  }
}
// code provided by PROGIEZ

1461. Check If a String Contains All Binary Codes of Size K LeetCode Solution in Python

class Solution:
  def hasAllCodes(self, s: str, k: int) -> bool:
    n = 1 << k
    if len(s) < n:
      return False

    # used[i] := True if i is a substring of `s`
    used = [0] * n

    windowStr = 0 if k == 1 else int(s[0:k - 1], 2)
    for i in range(k - 1, len(s)):
      # Include the s[i].
      windowStr = (windowStr << 1) + int(s[i])
      # Discard the s[i - k].
      windowStr &= n - 1
      used[windowStr] = True

    return all(u for u in used)
 # code by PROGIEZ