Welcome to Subscribe On Youtube

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

Description

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

Solutions

• Java
• C++
• Python
• Go
• TypeScript
• Java 2
• C++ 2
• Python 2
• Go 2
• TypeScript 2

• class Solution {
      public boolean hasAllCodes(String s, int k) {
          Set<String> ss = new HashSet<>();
          for (int i = 0; i < s.length() - k + 1; ++i) {
              ss.add(s.substring(i, i + k));
          }
          return ss.size() == 1 << k;
      }
  }
  

• class Solution {
  public:
      bool hasAllCodes(string s, int k) {
          unordered_set<string> ss;
          for (int i = 0; i + k <= s.size(); ++i) {
              ss.insert(move(s.substr(i, k)));
          }
          return ss.size() == 1 << k;
      }
  };
  

• class Solution:
      def hasAllCodes(self, s: str, k: int) -> bool:
          ss = {s[i : i + k] for i in range(len(s) - k + 1)}
          return len(ss) == 1 << k
  
  

• func hasAllCodes(s string, k int) bool {
  	ss := map[string]bool{}
  	for i := 0; i+k <= len(s); i++ {
  		ss[s[i:i+k]] = true
  	}
  	return len(ss) == 1<<k
  }
  

• function hasAllCodes(s: string, k: number): boolean {
      const n = s.length;
      const m = 1 << k;
      if (n - k + 1 < m) {
          return false;
      }
      const ss = new Set<string>();
      for (let i = 0; i + k <= n; ++i) {
          ss.add(s.slice(i, i + k));
      }
      return ss.size === m;
  }
  
  

• class Solution {
      public boolean hasAllCodes(String s, int k) {
          int n = s.length();
          int m = 1 << k;
          if (n - k + 1 < m) {
              return false;
          }
          boolean[] ss = new boolean[m];
          int x = Integer.parseInt(s.substring(0, k), 2);
          ss[x] = true;
          for (int i = k; i < n; ++i) {
              int a = (s.charAt(i - k) - '0') << (k - 1);
              int b = s.charAt(i) - '0';
              x = (x - a) << 1 | b;
              ss[x] = true;
          }
          for (boolean v : ss) {
              if (!v) {
                  return false;
              }
          }
          return true;
      }
  }
  
  

• class Solution {
  public:
      bool hasAllCodes(string s, int k) {
          int n = s.size();
          int m = 1 << k;
          if (n - k + 1 < m) {
              return false;
          }
          bool ss[m];
          memset(ss, false, sizeof(ss));
          int x = stoi(s.substr(0, k), nullptr, 2);
          ss[x] = true;
          for (int i = k; i < n; ++i) {
              int a = (s[i - k] - '0') << (k - 1);
              int b = s[i] - '0';
              x = (x - a) << 1 | b;
              ss[x] = true;
          }
          return all_of(ss, ss + m, [](bool v) { return v; });
      }
  };
  
  

• class Solution:
      def hasAllCodes(self, s: str, k: int) -> bool:
          n = len(s)
          m = 1 << k
          if n - k + 1 < m:
              return False
          ss = set()
          x = int(s[:k], 2)
          ss.add(x)
          for i in range(k, n):
              a = int(s[i - k]) << (k - 1)
              b = int(s[i])
              x = (x - a) << 1 | b
              ss.add(x)
          return len(ss) == m
  
  

• func hasAllCodes(s string, k int) bool {
  	n, m := len(s), 1<<k
  	if n-k+1 < m {
  		return false
  	}
  	ss := make([]bool, m)
  	x, _ := strconv.ParseInt(s[:k], 2, 64)
  	ss[x] = true
  	for i := k; i < n; i++ {
  		a := int64(s[i-k]-'0') << (k - 1)
  		b := int64(s[i] - '0')
  		x = (x-a)<<1 | b
  		ss[x] = true
  	}
  	for _, v := range ss {
  		if !v {
  			return false
  		}
  	}
  	return true
  }
  
  

• function hasAllCodes(s: string, k: number): boolean {
      const n = s.length;
      const m = 1 << k;
      if (n - k + 1 < m) {
          return false;
      }
      let x = +`0b${s.slice(0, k)}`;
      const ss = new Set<number>();
      ss.add(x);
      for (let i = k; i < n; ++i) {
          const a = +s[i - k] << (k - 1);
          const b = +s[i];
          x = ((x - a) << 1) | b;
          ss.add(x);
      }
      return ss.size === m;
  }
  
  

All Problems

All Solutions