Number of binary strings such that there is no substring of length â ‰¥ 3 | C # 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
using System ; class GFG { static long MOD = 1000000007 ; static long countStr ( int N ) { long [ , ] dp = new long [ N + 1 , 3 ] ; 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 ; } public static void Main ( ) { int N = 8 ; Console . WriteLine ( countStr ( N ) ) ; } }