Number of binary strings such that there is no substring of length â ‰¥ 3 | Python3 implementation of the approach ; Function to return the count of all possible binary strings ; Base cases ; dp [ i ] [ j ] is the number of possible strings such that '1' just appeared consecutively j times upto ith index ; Taking previously calculated value ; Taking all the possible cases that can appear at the Nth position ; Driver code
MOD = 1000000007 NEW_LINE def countStr ( N ) : NEW_LINE INDENT dp = [ [ 0 for i in range ( 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 = 8 NEW_LINE print ( countStr ( N ) ) NEW_LINE DEDENT