Count binary strings with k times appearing adjacent two set bits | Javascript program to count number of binary strings with k times appearing consecutive 1 's. ; dp [ i ] [ j ] [ 0 ] stores count of binary strings of length i with j consecutive 1 ' s ▁ and ▁ ending ▁ at ▁ 0 . ▁ ▁ dp [ i ] [ j ] [1 ] ▁ stores ▁ count ▁ of ▁ binary ▁ ▁ strings ▁ of ▁ length ▁ i ▁ with ▁ j ▁ consecutive ▁ ▁ 1' s and ending at 1. ; If n = 1 and k = 0. ; Number of adjacent 1 's can not exceed i-1 ; Driver code
function countStrings ( n , k ) { let dp = new Array ( n + 1 ) ; for ( let i = 0 ; i < n + 1 ; i ++ ) { dp [ i ] = new Array ( k + 1 ) ; for ( let j = 0 ; j < k + 1 ; j ++ ) { dp [ i ] [ j ] = new Array ( 2 ) ; for ( let l = 0 ; l < 2 ; l ++ ) { dp [ i ] [ j ] [ l ] = 0 ; } } } dp [ 1 ] [ 0 ] [ 0 ] = 1 ; dp [ 1 ] [ 0 ] [ 1 ] = 1 ; for ( let i = 2 ; i <= n ; i ++ ) { for ( let j = 0 ; j < i && j < k + 1 ; j ++ ) { dp [ i ] [ j ] [ 0 ] = dp [ i - 1 ] [ j ] [ 0 ] + dp [ i - 1 ] [ j ] [ 1 ] ; dp [ i ] [ j ] [ 1 ] = dp [ i - 1 ] [ j ] [ 0 ] ; if ( j - 1 >= 0 ) { dp [ i ] [ j ] [ 1 ] += dp [ i - 1 ] [ j - 1 ] [ 1 ] ; } } } return dp [ n ] [ k ] [ 0 ] + dp [ n ] [ k ] [ 1 ] ; } let n = 5 , k = 2 ; document . write ( countStrings ( n , k ) ) ;