Count N | Java program for the above approach ; Function to count binary strings of length N having substring "11" ; Initialize dp [ ] of size N + 1 ; Base Cases ; Stores the first N powers of 2 ; Generate ; Iterate over the range [ 2 , N ] ; Print total count of substrings ; Driver Code
import java . util . * ; class GFG { static void binaryStrings ( int N ) { int [ ] dp = new int [ N + 1 ] ; dp [ 0 ] = 0 ; dp [ 1 ] = 0 ; int [ ] power = new int [ N + 1 ] ; power [ 0 ] = 1 ; for ( int i = 1 ; i <= N ; i ++ ) { power [ i ] = 2 * power [ i - 1 ] ; } for ( int i = 2 ; i <= N ; i ++ ) { dp [ i ] = dp [ i - 1 ] + dp [ i - 2 ] + power [ i - 2 ] ; } System . out . println ( dp [ N ] ) ; } public static void main ( String [ ] args ) { int N = 12 ; binaryStrings ( N ) ; } }