text: Number of Binary Strings of length N with K adjacent Set Bits | Java program to find the number of Bit Strings of length N with K adjacent set bits ; Function to find the number of Bit Strings of length N with K adjacent set bits ; Base Case when we form bit string of length n ; if f ( bit string ) = k , count this way ; Check if the last bit was set , if it was set then call for next index by incrementing the adjacent bit count else just call the next index with same value of adjacent bit count and either set the bit at current index or let it remain unset ; set the bit at currentIndex ; unset the bit at currentIndex ; Driver Code ; dp [ i ] [ j ] [ k ] represents bit strings of length i with f ( bit string ) = j and last bit as k ; initialize the dp ; total ways = ( ways by placing 1 st bit as 1 + ways by placing 1 st bit as 0 )
code: class solution { static final int MAX = 1000 ; static int waysToKAdjacentSetBits ( int dp [ ] [ ] [ ] , int n , int k , int currentIndex , int adjacentSetBits , int lastBit ) { if ( currentIndex == n ) { if ( adjacentSetBits == k ) return 1 ; return 0 ; } if ( dp [ currentIndex ] [ adjacentSetBits ] [ lastBit ] != - 1 ) { return dp [ currentIndex ] [ adjacentSetBits ] [ lastBit ] ; } int noOfWays = 0 ; if ( lastBit == 1 ) { noOfWays += waysToKAdjacentSetBits ( dp , n , k , currentIndex + 1 , adjacentSetBits + 1 , 1 ) ; noOfWays += waysToKAdjacentSetBits ( dp , n , k , currentIndex + 1 , adjacentSetBits , 0 ) ; } else if ( lastBit == 0 ) { noOfWays += waysToKAdjacentSetBits ( dp , n , k , currentIndex + 1 , adjacentSetBits , 1 ) ; noOfWays += waysToKAdjacentSetBits ( dp , n , k , currentIndex + 1 , adjacentSetBits , 0 ) ; } dp [ currentIndex ] [ adjacentSetBits ] [ lastBit ] = noOfWays ; return noOfWays ; } public static void main ( String args [ ] ) { int n = 5 , k = 2 ; int dp [ ] [ ] [ ] = new int [ MAX ] [ MAX ] [ 2 ] ; for ( int i = 0 ; i < MAX ; i ++ ) for ( int j = 0 ; j < MAX ; j ++ ) for ( int k1 = 0 ; k1 < 2 ; k1 ++ ) dp [ i ] [ j ] [ k1 ] = - 1 ; int totalWays = waysToKAdjacentSetBits ( dp , n , k , 1 , 0 , 1 ) + waysToKAdjacentSetBits ( dp , n , k , 1 , 0 , 0 ) ; System . out . print ( " Number ▁ of ▁ ways ▁ = ▁ " + totalWays + "NEW_LINE"); } }