Count of Binary strings of length N having atmost M consecutive 1 s or 0 s alternatively exactly K times | C ++ program to find the count of Binary strings of length N having atmost M consecutive 1 s or 0 s alternatively exactly K times ; Array to contain the final result ; Function to get the number of desirable binary strings ; if we reach end of string and groups are exhausted , return 1 ; if length is exhausted but groups are still to be made , return 0 ; if length is not exhausted but groups are exhausted , return 0 ; if both are negative just return 0 ; if already calculated , return it ; initialise answer for each state ; loop through every possible m ; Driver code
#include <bits/stdc++.h> NEW_LINE using namespace std ; int dp [ 1000 ] [ 1000 ] ; int solve ( int n , int k , int m ) { if ( n == 0 && k == 0 ) return 1 ; if ( n == 0 && k != 0 ) return 0 ; if ( n != 0 && k == 0 ) return 0 ; if ( n < 0 k < 0 ) return 0 ; if ( dp [ n ] [ k ] ) return dp [ n ] [ k ] ; int ans = 0 ; for ( int j = 1 ; j <= m ; j ++ ) { ans += solve ( n - j , k - 1 , m ) ; } return dp [ n ] [ k ] = ans ; } int main ( ) { int N = 7 , K = 4 , M = 3 ; cout << solve ( N , K , M ) ; }