Skip to content

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

  • Time: $O(|\texttt{s}|)$
  • Space: $O(|\texttt{s}|)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
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; });
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
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);
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
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)