leetcode

commit cde9bd2098ed0a590271b4e26de48029677ff5ea
parent ec0c54a67a9d545c5173cbefe7ad466a519f3d19
Author: Jack Sangdahl <jack@pngu.org>
Date:   Sun, 22 Feb 2026 21:06:54 -0700

1461. check if a string contains all binary codes of size k

Diffstat:
A
check_str_contain_binary_code.c
 | 
42
++++++++++++++++++++++++++++++++++++++++++
A
check_str_contain_binary_code.py
 | 
18
++++++++++++++++++

2 files changed, 60 insertions(+), 0 deletions(-)
diff --git a/check_str_contain_binary_code.c b/check_str_contain_binary_code.c
@@ -0,0 +1,42 @@
+// 1461. Check If a String Contains All Binary Codes of Size K
+#include "leetcode.h"
+
+/*
+ * 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'.
+ */
+
+bool hasAllCodes(char *s, int k) {
+  int n = strlen(s), m = 1 << k, window = 0;
+  if (n < m)
+    return false;
+  bool *vis = (bool *)calloc(m, sizeof(bool));
+  if (k > 1)
+    for (int i = 0; i < k - 1; i++)
+      window = (window << 1) + (s[i] - '0');
+  for (int i = k - 1; i < n; i++) {
+    window = (window << 1) + (s[i] - '0');
+    window &= (m - 1);
+    vis[window] = true;
+  }
+  for (int i = 0; i < m; i++)
+    if (!vis[i]) {
+      free(vis);
+      return false;
+    }
+  free(vis);
+  return true;
+}
+
+int main() {
+  char *s1 = "00110110", *s2 = "0110", *s3 = "0110";
+  bool r1 = hasAllCodes(s1, 2);
+  bool r2 = hasAllCodes(s2, 1);
+  bool r3 = hasAllCodes(s3, 2);
+  printf("%d\n", r1); // expect: 1
+  assert(r1 == true);
+  printf("%d\n", r2); // expect: 1
+  assert(r2 == true);
+  printf("%d\n", r3); // expect: 0
+  assert(r3 == false);
+}
diff --git a/check_str_contain_binary_code.py b/check_str_contain_binary_code.py
@@ -0,0 +1,18 @@
+# 1461. 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'.
+"""
+
+
+class Solution:
+    def hasAllCodes(self, s: str, k: int) -> bool:
+        return len({s[i - k : i] for i in range(k, len(s) + 1)}) == 1 << k
+
+
+if __name__ == "__main__":
+    obj = Solution()
+    print(obj.hasAllCodes(s="00110110", k=2))
+    print(obj.hasAllCodes(s="0110", k=1))
+    print(obj.hasAllCodes(s="0110", k=2))