Data Structuresand Algorithms Good OldJava AdvancedInterview Topics Cloud andDatabases Web Designand Development Must-knowTools Good ToKnow

## Count strings without consecutive 1s

Problem: Given an integer N, count all the strings without consecutive 1s.
Assume that the strings are made up of only 0s and 1s

Solution: Let a be the number of strings without consecutive 1s and with last-character = 0

And let b be the number of strings without consecutive 1s but with last-character = 1

For a(k), we can append either 0 or 1 and the resulting strings would still be without consecutive 1s
For b(k), we can only append a 0 at the end.

Recursively, a(k+1) and b(k+1) can be written as:
a(k+1) = a(k) + b(k)
b(k+1) = a(k)

This is a perfect candidate for dynamic programming.
```int countStringsWithout1s(int n)
{
int a[n];
int b[n];

a = 1;
b = 1;

for (int i = 1; i < n; i++)
{
a[i] = a[i-1] + b[i-1];
b[i] = a[i-1];
}
return a[n-1] + b[n-1];
}
```

Like us on Facebook to remain in touch
with the latest in technology and tutorials!

Got a thought to share or found a
bug in the code?
We'd love to hear from you:

 Name: Email: (Your email is not shared with anybody) Comment: