Count number of binary strings such that there is no substring of length greater than or equal to 3 with all 1 's | C ++ implementation of the approach ; Function to return the count of all possible valid strings ; 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
#include <bits/stdc++.h> NEW_LINE using namespace std ; const long MOD = 1000000007 ; long countStrings ( long N ) { long dp [ N + 1 ] [ 3 ] ; memset ( dp , 0 , sizeof ( dp ) ) ; dp [ 1 ] [ 0 ] = 1 ; dp [ 1 ] [ 1 ] = 1 ; dp [ 1 ] [ 2 ] = 0 ; for ( int i = 2 ; i <= N ; i ++ ) { dp [ i ] [ 0 ] = ( dp [ i - 1 ] [ 0 ] + dp [ i - 1 ] [ 1 ] + dp [ i - 1 ] [ 2 ] ) % MOD ; dp [ i ] [ 1 ] = dp [ i - 1 ] [ 0 ] % MOD ; dp [ i ] [ 2 ] = dp [ i - 1 ] [ 1 ] % MOD ; } long ans = ( dp [ N ] [ 0 ] + dp [ N ] [ 1 ] + dp [ N ] [ 2 ] ) % MOD ; return ans ; } int main ( ) { long N = 3 ; cout << countStrings ( N ) ; return 0 ; }