Count number of binary strings such that there is no substring of length greater than or equal to 3 with all 1 's | Python3 implementation of the approach ; Function to return the count of all possible valid strings ; Initialise and fill 0 's in the dp array ; Base cases ; dp [ i ] [ j ] = number of possible strings such that '1' just appeared consecutively j times upto the ith index ; Taking previously calculated value ; Taking all possible cases that can appear at the Nth position ; Driver code
MOD = 1000000007 NEW_LINE def countStrings ( N ) : NEW_LINE INDENT dp = [ [ 0 ] * 3 for i in range ( N + 1 ) ] NEW_LINE dp [ 1 ] [ 0 ] = 1 ; NEW_LINE dp [ 1 ] [ 1 ] = 1 ; NEW_LINE dp [ 1 ] [ 2 ] = 0 ; NEW_LINE for i in range ( 2 , N + 1 ) : NEW_LINE INDENT dp [ i ] [ 0 ] = ( dp [ i - 1 ] [ 0 ] + dp [ i - 1 ] [ 1 ] + dp [ i - 1 ] [ 2 ] ) % MOD NEW_LINE dp [ i ] [ 1 ] = dp [ i - 1 ] [ 0 ] % MOD NEW_LINE dp [ i ] [ 2 ] = dp [ i - 1 ] [ 1 ] % MOD NEW_LINE DEDENT ans = ( dp [ N ] [ 0 ] + dp [ N ] [ 1 ] + dp [ N ] [ 2 ] ) % MOD NEW_LINE return ans NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT N = 3 NEW_LINE print ( countStrings ( N ) ) NEW_LINE DEDENT