Count of Binary strings of length N having atmost M consecutive 1s or 0s alternatively exactly K times

0 0 9 minutes read

Given three integers, N, K and M. The task is to find out the number of binary strings of length N which always starts with 1, in which there can be at most M consecutive 1’s or 0’s and they alternate exactly K times.
Examples:

Input: N = 5, K = 3, M = 2
Output: 3
The 3 configurations are:
11001
10011
11011
Explanation:
Notice that the groups of 1’s and 0’s alternate exactly K times
Input: N = 7, K = 4, M = 3
Output: 16

Approach: Since this problem involves both overlapping sub-problem and optimal substructure. So, this problem can be solved using dynamic programming.

Sub-problem: DP[i][j] represents the number of binary strings upto length i having j alternating groups till now. So, to calculate dp[N][K] if we know the value of dp[n-j][k-1], then we can easily get the result by summing up the sub-problem value over j = 1 to m (DP[N][K] represents the final answer).
As shown below in the recursion tree diagram, it is observed many sub-problem overlaps. So, the result needs to be cached to avoid redundant calculations.

Optimal substructure:
$$dp[i][j]=$$\sum_{j=1}^{M} f(N-j, K-1)$
By following the top-down DP approach:
As we can have a group which can be atmost of the length M, so we iterate on every possible length and recur with new N and decreasing K by 1, as a new group is formed. Solution to sub-problem is cached and summed up to give final result dp[N][K].
Base Case:
1. When N is 0 and K is 0, then return 1
2. When N is 0 but K is not 0, then return 0
3. When N is not 0 but K is 0, then return 0
4. When both are negative, return 0

Below is the implementation of above approach:

C++

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

Java

// Java program to find the count of 
// Binary Strings of length N having
// atmost M consecutive 1s or 0s
// alternatively exactly K times
import java.util.*;
 
class GFG{
 
// Array to contain the final result
static int [][]dp = new int[1000][1000];
 
// Function to get the number
// of desirable binary strings
static int solve(int n, int k, int m)
{
 
    // If we reach end of string
    // and groups are exhausted,
    // return 1
    if (n == 0 && k == 0)
        return 1;
 
    // If length is exhausted but
    // groups are still to be made,
    // return 0
    if (n == 0 && k != 0)
        return 0;
 
    // If length is not exhausted
    // but groups are exhausted,
    // return 0
    if (n != 0 && k == 0)
        return 0;
 
    // If both are negative
    // just return 0
    if (n < 0 || k < 0)
        return 0;
 
    // If already calculated,
    // return it
    if (dp[n][k] > 0)
        return dp[n][k];
 
    // Initialise answer
    // for each state
    int ans = 0;
 
    // Loop through every
    // possible m
    for(int j = 1; j <= m; j++)
    {
       ans += solve(n - j, k - 1, m);
    }
    return dp[n][k] = ans;
}
 
// Driver code
public static void main(String[] args)
{
    int N = 7, K = 4, M = 3;
    System.out.print(solve(N, K, M));
}
}
 
// This code is contributed by Rajput-Ji

Python 3

# Python3 program to find the count 
# of Binary strings of length N 
# having atmost M consecutive 1s or 
# 0s alternatively exactly K times 
 
# List to contain the final result 
rows, cols = (1000, 1000) 
dp = [[0 for i in range(cols)] 
         for j in range(rows)]
 
# Function to get the number 
# of desirable binary strings 
def solve(n, k, m):
     
    # If we reach end of string 
    # and groups are exhausted, 
    # return 1
    if n == 0 and k == 0:
        return 1
 
    # If length is exhausted but 
    # groups are still to be made, 
    # return 0 
    if n == 0 and k != 0: 
        return 0
 
    # If length is not exhausted 
    # but groups are exhausted, 
    # return 0 
    if n != 0 and k == 0: 
        return 0
 
    # If both are negative 
    # just return 0 
    if n < 0 or k < 0: 
        return 0
 
    # If already calculated, 
    # return it 
    if dp[n][k]:
        return dp[n][k]
 
    # Initialise answer 
    # for each state 
    ans = 0
 
    # Loop through every 
    # possible m 
    for j in range(1, m + 1):
        ans = ans + solve(n - j,
                          k - 1, m)
    dp[n][k] = ans
     
    return dp[n][k]
 
# Driver code 
N = 7
K = 4
M = 3
 
print(solve(N, K, M))
 
# This code is contributed by ishayadav181

C#

// C# program to find the count of 
// binary strings of length N having
// atmost M consecutive 1s or 0s
// alternatively exactly K times
using System;
 
class GFG{
 
// Array to contain the readonly result
static int [,]dp = new int[1000, 1000];
 
// Function to get the number
// of desirable binary strings
static int solve(int n, int k, int m)
{
 
    // If we reach end of string
    // and groups are exhausted,
    // return 1
    if (n == 0 && k == 0)
        return 1;
 
    // If length is exhausted but
    // groups are still to be made,
    // return 0
    if (n == 0 && k != 0)
        return 0;
 
    // If length is not exhausted
    // but groups are exhausted,
    // return 0
    if (n != 0 && k == 0)
        return 0;
 
    // If both are negative
    // just return 0
    if (n < 0 || k < 0)
        return 0;
 
    // If already calculated,
    // return it
    if (dp[n, k] > 0)
        return dp[n, k];
 
    // Initialise answer
    // for each state
    int ans = 0;
 
    // Loop through every
    // possible m
    for(int j = 1; j <= m; j++)
    {
       ans += solve(n - j, k - 1, m);
    }
    return dp[n, k] = ans;
}
 
// Driver code
public static void Main(String[] args)
{
    int N = 7, K = 4, M = 3;
     
    Console.Write(solve(N, K, M));
}
}
 
// This code is contributed by gauravrajput1

Javascript

<script>
 
// Javascript program to find the count of 
// Binary Strings of length N having
// atmost M consecutive 1s or 0s
// alternatively exactly K times
 
    // Array to contain the final result
     dp = Array(1000);
     for(i =0;i<1000;i++)
         dp[i] = Array(1000).fill(0);
 
    // Function to get the number
    // of desirable binary strings
    function solve(n , k , m) 
    {
 
        // If we reach end of string
        // and groups are exhausted,
        // return 1
        if (n == 0 && k == 0)
            return 1;
 
        // If length is exhausted but
        // groups are still to be made,
        // return 0
        if (n == 0 && k != 0)
            return 0;
 
        // If length is not exhausted
        // but groups are exhausted,
        // return 0
        if (n != 0 && k == 0){
            return 0;
            }
 
        // If both are negative
        // just return 0
        if (n < 0 || k < 0)
            return 0;
 
        // If already calculated,
        // return it
        if (dp[n][k] > 0)
            return dp[n][k];
 
        // Initialise answer
        // for each state
        var ans = 0;
 
        // Loop through every
        // possible m
        for (var j = 1; j <= m; j++) {
            ans += solve(n - j, k - 1, m);
           // document.write(ans);
        }
        return dp[n][k] = ans;
    }
 
    // Driver code
     
        var N = 7, K = 4, M = 3;
        document.write(solve(N, K, M));
 
// This code contributed by umadevi9616
 
</script>

Output

Time complexity: O(N*K*M)
Auxiliary Space: O(1000*1000)

Efficient approach : Using DP Tabulation method ( Iterative approach )

The approach to solve this problem is same but DP tabulation(bottom-up) method is better then Dp + memoization(top-down) because memoization method needs extra stack space of recursion calls.

Steps to solve this problem :

Create a DP to store the solution of the subproblems and initialize it with 0.
Initialize the DP with base cases dp[0][0] = 1.
Now Iterate over subproblems to get the value of current problem form previous computation of subproblems stored in DP
Return the final solution stored in dp[n][k].

Implementation :

C++

// C++ code for above approach 
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to get the number
// of desirable binary strings
int countBinaryStrings(int n, int k, int m) {
    vector<vector<int>> dp(n + 1, vector<int>(k + 1, 0));
     
    // initialize the base cases
    dp[0][0] = 1;
    for (int i = 1; i <= m && i <= n; i++) {
        dp[i][1] = 1;
    }
     
    // compute the remaining values
    for (int i = 1; i <= n; i++) {
        for (int j = 2; j <= k; j++) {
            for (int l = 1; l <= m && l <= i; l++) {
                  // update DP from previus stored values
                dp[i][j] += dp[i - l][j - 1];
            }
        }
    }
    // return final answer
    return dp[n][k];
}
 
int main() {
    int n = 7, k = 4, m = 3;
    cout << countBinaryStrings(n, k, m) << endl;
    return 0;
}
 
// --- by bhardwajji

Java

import java.util.*;
 
public class Main {
 
    // Function to get the number
    // of desirable binary strings
    static int countBinaryStrings(int n, int k, int m) {
        int[][] dp = new int[n + 1][k + 1];
         
        // initialize the base cases
        dp[0][0] = 1;
        for (int i = 1; i <= m && i <= n; i++) {
            dp[i][1] = 1;
        }
         
        // compute the remaining values
        for (int i = 1; i <= n; i++) {
            for (int j = 2; j <= k; j++) {
                for (int l = 1; l <= m && l <= i; l++) {
                    // update DP from previous stored values
                    dp[i][j] += dp[i - l][j - 1];
                }
            }
        }
        // return final answer
        return dp[n][k];
    }
 
    public static void main(String[] args) {
        int n = 7, k = 4, m = 3;
        System.out.println(countBinaryStrings(n, k, m));
    }
}

Python3

def countBinaryStrings(n, k, m):
    # initialize dp matrix
    dp = [[0] * (k + 1) for i in range(n + 1)]
     
    # initialize base cases
    dp[0][0] = 1
    for i in range(1, min(m+1, n+1)):
        dp[i][1] = 1
     
    # compute remaining values
    for i in range(1, n+1):
        for j in range(2, k+1):
            for l in range(1, min(m+1, i+1)):
                dp[i][j] += dp[i-l][j-1]
     
    # return final answer
    return dp[n][k]
 
# example usage
n = 7
k = 4
m = 3
print(countBinaryStrings(n, k, m))

C#

using System;
 
class Program
{
    // Function to count desirable binary strings
    static int CountBinaryStrings(int n, int k, int m)
    {
        // Initialize a 2D array for dynamic programming
        int[,] dp = new int[n + 1, k + 1];
 
        // Initialize base cases
        dp[0, 0] = 1;
        for (int i = 1; i <= m && i <= n; i++)
        {
            dp[i, 1] = 1;
        }
 
        // Compute the remaining values
        for (int i = 1; i <= n; i++)
        {
            for (int j = 2; j <= k; j++)
            {
                for (int l = 1; l <= m && l <= i; l++)
                {
                    // Update dp from previously stored values
                    dp[i, j] += dp[i - l, j - 1];
                }
            }
        }
 
        // Return the final answer
        return dp[n, k];
    }
 
    static void Main()
    {
        int n = 7, k = 4, m = 3;
        Console.WriteLine(CountBinaryStrings(n, k, m));
    }
}

Output

Time complexity: O(N*K*M)
Auxiliary Space: O(N*K)

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!