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

Problem #

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 indicies 0, 1, 3 and 2 respectively.

Example 2:

Input: s = "00110", k = 2
Output: true

Example 3:

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 4:

Input: s = "0110", k = 2
Output: false
Explanation: The binary code "00" is of length 2 and doesn't exist in the array.

Example 5:

Input: s = "0000000001011100", k = 4
Output: false

Constraints:

1 <= s.length <= 5 * 10^5
s consists of 0’s and 1’s only.
1 <= k <= 20

Summary #

Given a binary string s and an integer k . If every binary string of length k is a substring of s, return True; otherwise, return False.

Solution Approach #

Construct a mask and slide it over the entire binary string. Each time it slides, extract the k binary characters covered by the mask. You can use a map to store the decimal numbers converted from different binary strings, and finally check whether len(map) is equal to k. However, using a map for storage is relatively slow, so here it is replaced with a bool array. First construct an array of length k, then update the bool value corresponding to the decimal value in this bool array through the mask each time, and record how many binary numbers are still missing. When the remaining count equals 0, it means all binary strings have appeared, so directly output true; otherwise, output false after the loop finishes.

Code #

package leetcode

import "math"

func hasAllCodes(s string, k int) bool {
	need := int(math.Pow(2.0, float64(k)))
	visited, mask, curr := make([]bool, need), (1<<k)-1, 0
	for i := 0; i < len(s); i++ {
		curr = ((curr << 1) | int(s[i]-'0')) & mask
		if i >= k-1 { // the valid bits of mask have reached k bits
			if !visited[curr] {
				need--
				visited[curr] = true
				if need == 0 {
					return true
				}
			}
		}
	}
	return false
}