Every Bit Pattern Inside

Medium

You are given a string bits of zeros and ones and an integer width. Return True if every one of the 2^width binary codes of length width occurs in bits as a substring (a contiguous piece), and False otherwise.

Example 1

bits="0011101", width=2 → True

All four codes of width 2 appear: "00" at index 0, "01" at 1, "11" at 2 and "10" at 4.

Example 2

bits="1111", width=1 → False

The code "0" never appears.

Example 3

bits="0001011100", width=3 → True

Constraints

1 ≤ len(bits) ≤ 5·10⁵
bits consists only of '0' and '1'
1 ≤ width ≤ 20

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Bit Manipulation Hash Table String Hash Function Rolling Hash

Similar problems

Recurring Gene Windows Medium Two Words One Letter Apart Medium Evenly Mixed Digit Pieces Medium Longest Piece Seen Twice Medium Palindrome After a Few Fixes Medium

Input

bits="0011101", width=2

Expected

True

Run checks the first 3 tests in your browser. Submit checks all 105 tests on the server, hidden ones included.