This is a tutorial to solve the problem LeetCode#1461
- The length of string
s
is smaller thank
: We cannot find any binary string of lengthk
that is a substring ofs
, the function simply returns false. - The length of string
s
is greater than or equal tok
: We will attempt to check all substrings of lengthk
ins
. For each binary substring, we derive a corresponding decimal valuex
. Then we mark thex
-th element of a boolean arraya
astrue
. After going through all elements, we check if the whole array is markedtrue
. If it is, the function returnstrue
; otherwise, returnsfalse
.
First, you consider the substring s[0..k-1]
of s
(i.e. the k
-prefix of s
). You can calculate the corresponding x
value very easily:
- At first,
x
is zero. - For every character read from the string:
- shift left
x
by 1 bit (i.e.x = x*2
). - add 1 to
x
if the character is'1'
- shift left
- Mark
a[x]
true
For example your substring is 110
. At first x
is zero. You read the substring from left to right:
- '1':
x <<= 1
(x
is still 0), thenx += 1
(x
becomes 1) - '1':
x <<= 1
(x
becomes 2), thenx += 1
(x
becomes 3) - '0':
x <<= 1
(x
becomes 6), thenx += 0
(x
is still 6)
In the end, we have x
equal 6, which is exactly the decimal value of the binary string 110
Do that for the first k
characters and we will obtain the value x
for the first substring.
For the next substrings (i.e. s[1..k]
, s[2..k+1]
, etc.), the idea is a little bit different, but quite similar.
- Keep
x
as the decimal value ofs[0..k-1]
- For each character read from the string:
- shift left
x
by 1 bit (i.e.x = x*2
) - if
x
is greater than or equal to1 << k
, makex -= (1 << k)
- add 1 to
x
if the character is'1'
- mark
a[x]
true
- shift left
Notice that we have an extra step. If x
is greater than or equal to 1 << k
(this C++ notation means ), that means
x
has used more than k
bits, we need to substract x
by 1 << k
to keep x
only using k
bits. For example we have k
equal 3, thus any number larger than or equal to uses more than 3 bits. (8 is
1000
, 9 is 1001
, 12 is 1100
, etc.)
It is also important to note that, substracting a random number by 1 << k
does not guarantee to make that number using at most k
bits. However, as we started with x
less than 1 << k
, and every time the number of bits that x
uses exceeds k
, substracting will make sure x
using at most k
bits. There will not be a point in our algorithm where x
uses k+2
bits.
After step 2.1, x
is even. After step 2.2, if x
is changed, it is subtracted by 1 << k
, which is itself an even number. Thus at step 2.3, x
is even. Adding 1 to x
will not make it using more bits.
For the solution described above:
- The space complexity is
(mainly because we need an array to mark which
x
value showed up) - The time complexity is
(iterate over the string)
Note that bit-shifting operator (e.g. x << 1
) is faster than normal multiplication (e.g. x * 2
). The attached C++ code above has remarkable performance:
- Runtime: 144 ms, faster than 98.81% of C++ online submissions for Check If a String Contains All Binary Codes of Size K.
- Memory Usage: 17.8 MB, less than 97.21% of C++ online submissions for Check If a String Contains All Binary Codes of Size K.