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

  • 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;
    }
    
    

All Problems

All Solutions