Count Binary Strings Without Consecutive Ones

November 6, 2021

Count Binary Strings Without Consecutive Ones

In Count Binary Strings Without Consecutive Ones problem we have to count strings of length n such that each character of the string can only be 1 or 0. And we should not count strings with ’11’ as a sub string. Here is a C++ implementation of both top down and bottom up approach.

Count Binary Strings Without Consecutive Ones Problem Statement

Given an integer n return the number of binary strings of length n such that they do not contain ’11’ as a sub string. The answer can be large so return the result modulo 1000000007.

Example:

Given n = 3

Output:

Explanation

The length 3 possible binary strings are – 000, 001, 010, 011, 100, 101 , 110, 111

Out of these 011, 110 and 111 contain 11 as a sub string. Therefore the result is 5.

Count Binary Strings Without Consecutive Ones Solution

Solution 1 (Top Down dynamic programming)

For writing the top down solution we will write a function F(id , prev).

F(id , prev) means number of binary strings of length n with prev filled at (n+1)th place. Now we have to decide our transitions.

The transitions will be :-

f(n,prev) = f(n-1,0) + f(n-1,1) if(prev ==0)

f(n,prev) = f(n-1,0) if(prev==1)

We will be using a memo table to speed up the solution and avoid recalculation of values.

C++ Code

#include <bits/stdc++.h>
#define ll long long
#define MOD 1000000007
using namespace std;
ll memo[100001][2];
ll solve(int n, int prev)
{
    if (n == 0)
        return 1;
    if (memo[n][prev] != –1)
        return memo[n][prev];
 
    ll op1 = 0, op2 = 0;
    op1 = solve(n – 1, 0);
    if (prev != 1)
        op2 = solve(n – 1, 1);
    return memo[n][prev] = (op1 + op2) % MOD;
}
int main()
{
    memset(memo, –1, sizeof memo);
    int n;
    cin >> n;
    cout << solve(n, 0) << endl;
 
    return 0;
}

Output:

2
3

Solution 2 (Bottom up Dynamic Programming)

For writing bottom up dp solution we will create a dp table as dp[n+1][2].

dp[i][0] gives us the count of binary strings of length i with ith charactor filled 0. dp[i][0] = dp[i-1][0] + dp[i-1][1]

dp[i][1] gives us the count of binary strings of length i with ith charactor filled 1. dp[i][1] – dp[i-1][0] (Because we don’t need consecutive ones).

Our answer will be dp[n][0]+dp[n][1].

C++ Code

#include <bits/stdc++.h>
#define ll long long
#define MOD 1000000007
using namespace std;
ll solve(int n)
{
    ll dp[n + 1][2];

    dp[1][0] = 1;
    dp[1][1] = 1;

    for (int i = 2; i <= n; i++)
    {
        dp[i][0] = (dp[i – 1][1] + dp[i – 1][0]) % MOD;
        dp[i][1] = (dp[i – 1][0]);
    }
    return (dp[n][0] + dp[n][1]) % MOD;
}
int main()
{
    int n;
    cin >> n;
    cout << solve(n) << endl;
    return 0;
}

Output:

3
5