Talking of our next problem that is "Count Binary Strings", is counted in a whole different group of our problem solving methods of recursion. We call this trick 'Include Exclude Sign', which we will discuss in this and a couple of further problems.

In this problem you are given a number n. All we need to print is the number of binary strings of length n with no consecutive 0's

For example:

Sample Input: 3

Sample Output: 5

How 5?

We have a total of eight binary numbers for length 3, out of which we have 5 numbers in which there are no consecutive zeros.

Approach :

We will use the 'Include Exclude Sign' trick to handle this problem. Just like in Tabulation, where we first assign Storage and Meaning, then Direction and finally Travel and Solve.

Let's assume two arrays, with n+1 length. Both these arrays will store the count of appropriate binary strings of length i at ith index but one stores the count of strings ending with Zero and another stores the count of strings ending with One.

Suppose n = 4, let's take a look at both the arrays with corresponding value of count at ith index of the string of i length.

In this figure, when length of string is 0, then there will be 0 strings with no consecutives 0. When at index 1, there will be 1 string in each array of length1 that is 0 and 1 respectively.

Now, when at index = 2, if we append 0 at the end of strings which we found at the last index in dp1[] then we will get all strings of length 2 ending with 0 at 2^{nd} index of dp0[]. And similarly if we append 1 at the end of strings which we found at the last index in dp0[] and dp1[]then we will get all strings of length 2 ending with 1 at 2^{nd} index of dp1[] with no consecutive 0.

As we move forward, we fill our array with same logic, which we generalize as:

dp0[i] = dp1[i-1]

dp1[i]I = dp0[i-1] +dp1[i-1]

You can see all the possible strings and count at any index in figure.

Strings ending with 1 contribute to both the array as after appending 1 or 0 it remains harmless and does not violate conditions of consecutive 0s.

But Strings ending with 0 contribute to only dp1[] array as after appending 1 it does not violate conditions of consecutive 0s.

Let's try to code this.

Yes! That looks good. But we can still make it better. How?

Instead of using 2 arrays of n length, we can simply use two variables, one keeping the count of zeroes and another keeping the count of ones, both initialized to 1. And then applying the for loop from 2 to n and defining two variables inside for loop, nzeroes and nones representing new and updated values of zeroes and ones with similar logic that we used above.

int nzeroes = ones;

int nones = ones + zeroes;

Let's code this one.

You can also watch part of the solution video.

import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws Exception {
Scanner scn = new Scanner(System.in);
int n = scn.nextInt();
int zeroes = 1;
int ones = 1;
for(int i = 2; i <= n; i++){
int nzeroes = ones;
int nones = ones + zeroes;
zeroes = nzeroes;
ones = nones;
}
System.out.println(zeroes + ones);
}
}

java;
true";

Analysis

Time Complexity :

The time complexity of this procedure is O(n) where n is the length of an array.

SPACE COMPLEXITY :

Since we have used two integer variables which take constant space, instead of two arrays of size n + 1, hence we are able to reduce the space complexity from O(n ) to O(1)since we have not used any extra memory or any extra data structure.

We hope that this article was helpful. Our team has really explained this question in a beautiful way. You must check out the solution video for more clear understanding.

Be kind to yourself. Don't lose hope. Best is yet to come.

Until then keep solving and learning new problems on Dynamic Programming.