How many bit strings are there of length 6 are there that do

How many bit strings are there of length 6 are there that do not contain “1111” as a substring

Solution

Number of bits string that contains 1111 = 6

The string patterns are (001111,011110, 111100,111111,111110,011111)

Number of bit strings of length 6 that don\'t contain 1111 as a substring = 2^6 - 6 = 64 - 6 = 58 substrings