Editorialist: Ayush Kapadia
Prequisite : Basic Recursion Concepts
Problem Link:
Short Description: Count number of binary strings of length n having “11011” as substring.
Explanation :
There are basically 2 major ways to solve this type of problem. They are :
(1) By actually generating the string character by character from an empty string keeping all contraints in mind.
(2) By iterating over all possible strings and count only those that satisfies our constraints.
The second method takes huge amount of time. For example in case of n = 9, you will have to check 512 string which is tedious for pen and paper based exam (However this approach is feasible to solve using computer)
So let us discuss first approach in detail with this question in mind. Later you can apply this technique to other questions also.
Generator Method :
Overview :
In this method we start generating the string character by character. It is recursive type of algorithm. First we look at the choices for first character. Based on that we will recursively call the function for size less than that given in problem. For example suppose problem asks to count number of English letter words having character 'A' in the word. So for this problem we can have 26 choices for first letter. If we choose 'A' as our first letter , then for rest of letters we can put anything we want , so if first letter is 'A', then count is 26^(n-1). However if first letter is not 'A' , then ofcourse there has to be 'A' in remaning (n-1) letters. So the problem becomes same for size (n-1). Thus recursion equation becomes f(n) = (1)*(26\wedge(n-1)) + (25)*(f(n-1)).
There actually arises three cases at every point.
Case – 1) Constraints already satisfied (i.e Substring already formed from characters we generated) Answer is total possible strings you can form from remaining characters
Case – 2) Not a single part of constarint satisfied (i.e. our substring cannot start from any of characters we generated till now). Answer is F(remaning characters)
Case – 3) Partial constarint is specified (i.e substring can start from characters generated uptill now)
Answer is either solve subcases or make a seperate generator function so that you can recurse for similiar contraints for lower problem size.
So for any problem of this type, we have to first found some recursive equations based on cases described above. And then use your understanding for getting the answer through recursion equation.
Solution to our problem
We have to generate binary string of length n. So let us generate that.
Case 0: First digit is 0
Then substring “11011” definitely cannot start at first digit. So substring has to be found in remaining (n-1) binary digits. So problem basically reduces to counting number of strings of length n-1. So for this case it is F(n-1)
Case 1: First digit is 1
Case 1.1 : Second digit is 0
Then the same conclusion. Substring cannot start at 0th digit as well as 1st digit. So problem reduces to counting number of strings of length n-2 . F(n-2)
Case 1.2 : Second digit is 1
We will be using special generator function for this subcase (for counting strings with first two digits as “11”. ) The reason you will soon understand. G(n)
Lets call our special generator function be G(n) and our original function be F(n).
So F(n) = F(n-1) + F(n-2) + G(n)
So if we know G(n) and all previous values of F(n) then it is very easy to calculate F(n). But the question is how to calculate G(n)
So lets generate G(n)
Case 0: Third digit is 1
Now the problem arises, substring can still start at second digit or third digit. So we cannot ignore that. So now what to do. Think deep. The problem is nothing again but the same G function with length n – 1. This because now you have “111” as start . Ofcourse you know substring cannot start at 1st digit. But it can start at 2nd or third digit. This is same as G(n-1) (You have to generate string of length n-1 with start as “11” ). (Remember first digit is of no use in this case) G(n-1)
Case 1 : Third digit is 0
Case 1.1 : Fourth digit is 0
So now you have “1100” at start. Ofcourse you cannot have substring at 1st,2nd , 3rd or 4th digit. So problem basically reduces to counting number of strings of length n-4. F(n-4)
Case 1.2 : Fourth digit is 1
Case 1.2.1 : Fifth digit is 0
So now you have “11010” at start. Ofcourse you cannot have substring at 1st,2nd , 3rd or 4th or 5th digit. So problem basically reduces to counting number of strings of length n-5. F(n-5)
Case 1.2.2 : Fifth digit is1
So you have found the substring. So remaning can be anything. So 2^(n-5)
So G(n) = G(n-1) + F(n-4) + F(n-5) + 2\wedge (n-5)
Thus knowing function F and G values at previous points, you can easily calculate it.
So final equation becomes :
F(n) = F(n-1) + F(n-2) + G(n)
G(n) = G(n-1) + F(n-4) + F(n-5) + 2\wedge(n-5)
You can easily solve this using recursion.
Base Case : F(5) = 1 and G(5) =1
F(n) = G(n) = 0 , for n<5
For your reference here is the table you will get :
n | \;F(n) \;\;G(n)
------------------
5 | \;\:\;\;\; 1 \;\;\;\;\;\;\;1
6 | \;\;\;\;\; 4 \;\;\;\;\;\;\;3
7 | \;\;\;\;\;12 \;\;\;\;\;7
8 | \;\;\;\;\;31 \;\;\;\;\;15
9 | \;\;\;\;\;75 \;\;\;\;\;32
10 | \;\;\;175 \;\;\;\;69
11 | \;\;\;399 \;\;\;\;149
