Count of all Possible N Length Balanced Binary Strings

Intuition

Count of all Possible N Length Balanced Binary Strings. From the first condition of a balanced binary string, we can understand that it is not possible to generate a balanced binary string of an odd length. So, for an odd value of 'N,' the number of balanced binary strings will always be 0(zero). Now we need an approach for the even values of 'N' only.

• For even 'N,' there will always be 'N / 2' balanced pairs of '0's and '1's. So we can try to generate a formula by observing the results.
• For N = 0, the string will be empty, so only one possible balanced binary string.
• For N = 2, only "01" will be possible, so only one possible balanced binary string.
• For N = 4, possible balanced binary strings will be “0011” and “0101”, i.e., 2.
• For N = 6, the possible balanced binary string will be “000111”, “001011”, “010011”, “001101”, and “010101”, i.e., 5.

So observing the sequence of results: 1, 1, 2, 5, and so on. We can conclude that it is the sequence of Catalan Numbers. Matching out the results with indices of Catalan Numbers, we can generalize the Count of balanced binary strings for even 'N' as:

No. of Balanced Binary Strings of ‘N’ length = ‘N / 2’th Catalan Number 

Also see, Euclid GCD Algorithm

Basic Approach

To count all Possible N Length Balanced Binary Strings. Count the repeated character. The number of substrings with the same number of 0s and 1s and successive grouping is equal to the prior count if the current count is larger than the previous count. Because they lack a counterpart in the preceding substring, further 1s or 0s in the CURRENT count are NOT tallied.

The number of substrings is equal to the current count if the current count is lower than the prior count. Because they don't have a counterpart in the current substring, further 1s or 0s in the PREVIOUS count are not counted.

C++ implementation

//C++ programme for Count of all Possible N Length Balanced Binary Strings


#include <bits/stdc++.h>


using namespace std;


#define FIX_NUM 500
#define mod_num 1000000007


// Vector arr_vec to take a number
vector < long long int > arr_vec(FIX_NUM + 1, 0);


// Function functionToCountString  to get the  Number
void functionToCountString() {
    arr_vec[0] = 1;
    arr_vec[1] = 1;


  for (int i = 2; i < FIX_NUM + 1; i++) {
    long long int zero = 0;
      for (int j = 0; j < i; j++) {
        zero += ((arr_vec[j] % mod_num) *
          (arr_vec[i - 1 - j] % mod_num) %
          mod_num);
    }
    arr_vec[i] = (zero % mod_num);
  }
}


int totalBalancedStrings(int input_length) {
  // If N is odd
    if (input_length & 1) {
    return 0;
    }
  
  // retunring n/2 
     return arr_vec[input_length / 2];
}

// Main Section
int main() {
  
      functionToCountString();
      int input_length = 0;
      cout << "Enter length for balance binary string" << endl;
      cin >> input_length;
      cout << totalBalancedStrings(input_length);
}

Input

4

Output

2 

Complexity Analysis

Time Complexity:

O(N²), where ‘N’ is the length of the String. 

Explanation:

In the functionToCountString(), there are two nested for loops to calculate String Numbers take a total of O(N²) time.

Auxiliary Space

O(N), where 'N' size of the balanced binary string.

Explanation: 

Vector used to store ‘N’ Numbers occupies O(N) space.

Dynamic Programming

Following the intuition, we always have to do work for even 'N,' i.e., calculate the  'N / 2'th Catalan Number to get the total possible N length Balanced Binary Strings. There are many ways to count all Possible N Length Balanced Binary Strings.

Catalan Numbers can be described with the below formula:

So we can simply run two loops, the outer loop iterating for 'i' from 0 to 'N' and the inner one calculating ith Catalan number. This can be more understood with the below program.

Program

// C++ program to count the number of balanced binary strings.
#include <iostream>
#include <vector>
using namespace std;
 
// Function to calculate the Nth Catalan Number with Dynamic Programming.
long long catalanNumberDP(int N)
{
   // Vector to store the 'N' Catalan numbers.
   vector<long long> catalan(N + 1, 0);
 
   // The base values for Catalan numbers.
   catalan[0] = 1;
   catalan[1] = 1;
 
   // Calculating Catalan numbers from 2 to N.
   for (int i = 2; i <= N; i++)
   {
       for (int j = 0; j < i; j++)
           catalan[i] += catalan[j] * catalan[i - j - 1];
   }
 
   // Return the Nth Catalan number.
   return catalan[N];
}
 
// Main function.
int main()
{
   // Variable to store the size of the balanced binary string.
   int N;
   cout<<"Enter the number:”;
   cin>> N;
   cout<< "Number of Balanced Binary Strings for N = " << N << " are ";
 
   // For odd 'N,' the answer will always be 0, as no string is possible.
   if (N % 2)
       cout<< 0;
   else
   {
       // For even 'N', print the 'N / 2'th Catalan Number.
       cout<< catalanNumberDP(N / 2);
   }
}

Output

Enter the number : 10
Number of Balanced Binary Strings for N= 10 are 42

Complexity Analysis

Time Complexity:

O(N²), where ‘N’ is the size of the balanced binary string.

Explanation:

In the function catalanNumberDP(), the two loops used to calculate Catalan Numbers take a total of O(N²) time.

Auxiliary Space

O(N), where 'N' size of the balanced binary string.

Explanation: 

Vector used to store ‘N’ Catalan Numbers occupies O(N) space.

Using Binomial Coefficient

The below formula can also be used to find the Nth Catalan Number:

The Binomial Coefficient also represents the number of possible possibilities for selecting k things from a set of n objects, i.e., k-combinations of an n-element set.

We only need to calculate the binomial coefficient nCr. The standard formula for finding the value of binomial coefficients that uses recursive call is −

c(n,k) = c(n-1 , k-1) + c(n-1, k)

c(n, 0) = c(n, n) = 1,

which can be calculated with the below program.

Program

// C++ program to count the number of balanced binary strings.
#include <iostream>
#include <vector>
using namespace std;

// Function to calculate binomial coefficient 'nCr'.
long long binomialCoefficient(int n, int r)
{
   // Variable to store binomial Coefficient.
   long long nCr = 1;

   // As C(n, r) = C(n, n-r).
   r = max(r, n - r);

   for (int i = 0; i < r; i++)
   {
       nCr = nCr * (n - i);
       nCr = nCr / (i + 1);
   }

   // Returning the final result.
   return nCr;
}

//Function to calculate the Nth Catalan number by using binomial Coefficient.
long long catalanNumber(int N)
{
   // Calculating value of 2N C N.
   long long nCr = binomialCoefficient(2 * N, N);

   // Nth catalan number.
   long long catalan = nCr / (N + 1);

   // Returning result.
   return catalan;
}

// Main function.
int main()
{
   // Variable to store the size of the balanced binary string.
   int N;
   cout<<"Enter the number:";
   cin >> N;
   cout << "Number of Balanced Binary Strings for N = " << N << " are ";

   // For odd 'N,' the answer will always be 0, as no string is possible.
   if (N % 2)
       cout << 0;
   else
   {
       // For even 'N', print the 'N / 2'th Catalan Number.
       cout << catalanNumber(N / 2);
   }
}

Output

Enter the number : 10
Number of Balanced Binary Strings for N= 10 are 42

Complexity Analysis

Time Complexity

O(N), where 'N' represents the size of the balanced binary string.

Explanation: In the Function binomial coefficient(), the loop calculating the Binomial Coefficient takes a total of O(N) time.

Auxiliary Space

O(1)

Explanation: No extra space is getting used.

Check out this article - Balanced Parentheses

Frequently Asked Questions

What do you mean by the binary string?

A binary string is made up of a series of bytes. A binary string is usually used to hold non-traditional data, unlike a character string, which normally contains text data. The number of bytes in a binary string determines its length.

What do you mean by a fixed-length binary string?

The length property is supplied when fixed-length binary-string separate types, columns, and variables are declared, and all values have the same length. The length attribute for a fixed-length binary string must be between 1 and 32 766 inclusive.

What do you mean by a varying-length binary string?

The maximum length is given when varying-length binary-string separate types, columns, and variables are formed, which becomes the length attribute. The length of actual values may be shorter. The length property for a varying-length binary string must be between 1 and 32 740 bytes inclusive.

How is string represented in binary?

The byte representation is given by encoding, and you should encode the string to obtain a byte array. This is the byte-by-byte representation of your data.

How many bytes are in a binary character?

Eight characters make up a binary number, and each character is either a 1 or a 0. The value of each location is indicated by where the 1 is placed, and this information is utilised to get the overall value of the binary number. The eight letters are arranged so that each location corresponds to a certain fixed numerical value, as seen below.

Conclusion

In this blog, we learn about the problem Count of all Possible N Length Balanced Binary Strings, in which we have used DP to code the problem.

• Count the number of trees in a forest
• Printing Eulerian path using fleurys algorithm
• Check if there is a path between the two vertices in a directed graph.

Recommended problems -

• Binary Array Sorting
• Vertical Order Traversal of a Binary Tree
• Leaf Nodes in Binary Tree

Refer to our guided paths on Coding Ninjas Studio to learn more about DSA, Competitive Programming, JavaScript, System Design, etc. Enrol in our courses and refer to the mock test and problems available. Take a look at the interview experiences and interview bundle for placement preparations.

 Happy Learning Ninja! 🥷