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

Medium • View on LeetCode • View on GitHub

String Hash Table Bit Manipulation Hash Function Rolling Hash

Problem 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.

Solution

/**
 * @param {string} s
 * @param {number} k
 * @return {boolean}
 */
var hasAllCodes = function(s, k) {
  const requiredCount = 1 << k;
  const seenCodes = new Set();

  for (let i = 0; i <= s.length - k; i++) {
    seenCodes.add(s.slice(i, i + k));
    if (seenCodes.size === requiredCount) return true;
  }

  return false;
};