# PROBLEM LINK:

* Editorialist:* Rohit Mazumder

# PREREQUISITES:

Basic Dynamic Programming

# PROBLEM:

A binary string is considered as ‘Good’ when the pattern 0011 is concatenated k times (k≥1). Given a binary string B, find the number of ‘Good’ subsequences present in the string B. A subsequence is formed by dropping some characters from the initial string and keeping

the relative order of the remaining characters same.

# EXPLANATION:

Let **m** = Length of String B,

**n** = Length of String A.

Let *f(m,n)* be the number of times the string A occurs as a subsequence in String B.

**Case 1:**

Consider the following example:

B = 001001101

A = 0011

**Note that a subsequences ‘0011’ in string B can be formed by appending a ‘1’ at the end of each of the subsequences ‘001’ in the string ‘00100110’.**

So, if the last character of both the strings are the same, we can match them and move on to calculate for the rest of string B and string A, i.e. calculate *f(m-1, n-1).*

**We can also ignore the last character of string B (i.e. delete it!) and search for the subsequence A in the rest of the string B, i.e, we can recur for f(m-1, n).**

So, the number of subsequence ‘0011’ present in the substring ‘00100110’(here we have ignored the last character of B) =

*f(m-1,n)*

Hence, the last characters being the same, we get,

The total number of subsequences of the string ‘0011’ in B =

*f(m ,n) = f(m-1, n-1) + f(m-1, n)*

**Case 2:**

If the last characters of string A and B are different, we can ignore the last character of B and proceed to calculate the number of subsequence of A in the remaining portion of the string B i.e, recur for *f(m-1,n)*

Combining both the cases, the final recurrences for this problem is:

*f(m,n) = f(m-1,n-1) + f(m-1,n); Last characters are same*

*and*

*f(m,n) = f(m-1, n); Last characters are different*

**Base Case for the above recurrence:**

*f(m, 0)* = 1 ; Since the number of empty subsequence in a given string is 1 (for **m** ≥ 0)

*f(0, n)* = 0 ; Number of subsequences of A in an empty string is 0 (for **n** ≥ 1)

Now in this question we have been asked to calculate the value of * f* for

**A**in B for all

^{k}**k**≥ 1.

So to proceed we need to first find the maximum possible value of

**k**for

**A**to be a subsequence in B.

^{k}Then the answer is total number of good subsequences = number of subsequences as

**A**+ number of subsequences as

**A**+ number of subsequences as

^{2}**A**+…+ number of subsequences as

^{3}**A**=

^{k}*f(m, 4) + f(m,8) + f(m,12) + f(m,16) + ….+f(m,4k)*

**Subtask 1:**

B = 001001101; m = 9

Since m = 9, the maximum length of a good subsequence in B is 8 and k = 2.

i.e, the longest possible good subsequence in B is 00110011;

So, A = 00110011; n = 8, k=2

**Step 1:** Fill in the base cases

0(‘_’) | 1(‘0’) | 2(‘0’) | 3(‘1’) | 4(‘1’) | 5(‘0’) | 6(‘0’) | 7(‘1’) | 8(‘1’) | |
---|---|---|---|---|---|---|---|---|---|

0(‘_’) | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |

1(‘0’) | 1 | ||||||||

2(‘0’) | 1 | ||||||||

3(‘1’) | 1 | ||||||||

4(‘0’) | 1 | ||||||||

5(‘0’) | 1 | ||||||||

6(‘1’) | 1 | ||||||||

7(‘1’) | 1 | ||||||||

8(‘0’) | 1 | ||||||||

9(‘1’) | 1 |

**Step 2:** Fill according the recurrence derived

0(‘_’) | 1(‘0’) | 2(‘0’) | 3(‘1’) | 4(‘1’) | 5(‘0’) | 6(‘0’) | 7(‘1’) | 8(‘1’) | |
---|---|---|---|---|---|---|---|---|---|

0(‘_’) | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |

1(‘0’) | 1 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |

2(‘0’) | 1 | 2 | 1 | 0 | 0 | 0 | 0 | 0 | 0 |

3(‘1’) | 1 | 2 | 1 | 1 | 0 | 0 | 0 | 0 | 0 |

4(‘0’) | 1 | 3 | 3 | 1 | 0 | 0 | 0 | 0 | 0 |

5(‘0’) | 1 | 4 | 6 | 1 | 0 | 0 | 0 | 0 | 0 |

6(‘1’) | 1 | 4 | 6 | 7 | 1 | 0 | 0 | 0 | 0 |

7(‘1’) | 1 | 4 | 6 | 13 | 8 | 0 | 0 | 0 | 0 |

8(‘0’) | 1 | 4 | 6 | 13 | 8 | 8 | 0 | 0 | 0 |

9(‘1’) | 1 | 5 | 10 | 23 | 21 | 8 | 0 | 0 | 0 |

**Step 3:**

Answer = Number of subsequences ‘0011’ + Number of subsequences ‘00110011’

= f(9,4)+f(9,8) = 21 + 0 = **21**

**Subtask 2:**

B = 100110101010011

A = 001100110011

0(‘_’) | 1(‘0’) | 2(‘0’) | 3(‘1’) | 4(‘1’) | 5(‘0’) | 6(‘0’) | 7(‘1’) | 8(‘1’) | 9(‘0’) | 10(‘0’) | 11(‘1’) | 12(‘1’) | |
---|---|---|---|---|---|---|---|---|---|---|---|---|---|

0(‘_’) | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |

1(‘1’) | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |

2(‘0’) | 1 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |

3(‘0’) | 1 | 2 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |

4(‘1’) | 1 | 2 | 1 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |

5(‘1’) | 1 | 2 | 1 | 2 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |

6(‘0’) | 1 | 3 | 3 | 2 | 1 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |

7(‘1’) | 1 | 3 | 3 | 5 | 3 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |

8(‘0’) | 1 | 4 | 6 | 5 | 3 | 4 | 1 | 0 | 0 | 0 | 0 | 0 | 0 |

9(‘1’) | 1 | 4 | 6 | 11 | 8 | 4 | 1 | 1 | 0 | 0 | 0 | 0 | 0 |

10(‘0’) | 1 | 5 | 10 | 11 | 8 | 12 | 5 | 1 | 0 | 0 | 0 | 0 | 0 |

11(‘1’) | 1 | 5 | 10 | 21 | 19 | 12 | 5 | 6 | 1 | 0 | 0 | 0 | 0 |

12(‘0’) | 1 | 6 | 15 | 21 | 19 | 31 | 17 | 6 | 1 | 1 | 0 | 0 | 0 |

13(‘0’) | 1 | 7 | 21 | 21 | 19 | 50 | 48 | 6 | 1 | 2 | 1 | 0 | 0 |

14(‘1’) | 1 | 7 | 21 | 42 | 40 | 50 | 48 | 54 | 7 | 2 | 1 | 1 | 0 |

15(‘1’) | 1 | 7 | 21 | 63 | 82 | 50 | 48 | 102 | 61 | 2 | 1 | 2 | 1 |

Answer = f(15,4) + f(15, 8) + f(15, 12) = 82 + 61 + 1 = **144**

**Subtask 3 :**

B = 01011000101001001

A = 0011001100110011

0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | |
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|

0(‘_’) | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |

1(‘0’) | 1 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |

2(‘1’) | 1 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |

3(‘0’) | 1 | 2 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |

4(‘1’) | 1 | 2 | 1 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |

5(‘1’) | 1 | 2 | 1 | 2 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |

6(‘0’) | 1 | 3 | 3 | 2 | 1 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |

7(‘0’) | 1 | 4 | 6 | 2 | 1 | 2 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |

8(‘0’) | 1 | 5 | 10 | 2 | 1 | 3 | 3 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |

9(‘1’) | 1 | 5 | 10 | 12 | 3 | 3 | 3 | 3 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |

10(‘0’) | 1 | 6 | 15 | 12 | 3 | 6 | 6 | 3 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |

11(‘1’) | 1 | 6 | 15 | 27 | 15 | 6 | 6 | 9 | 3 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |

12(‘0’) | 1 | 7 | 21 | 27 | 15 | 21 | 12 | 9 | 3 | 3 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |

13(‘0’) | 1 | 8 | 28 | 27 | 15 | 36 | 33 | 9 | 3 | 6 | 3 | 0 | 0 | 0 | 0 | 0 | 0 |

14(‘1’) | 1 | 8 | 28 | 55 | 42 | 36 | 33 | 42 | 12 | 6 | 3 | 3 | 0 | 0 | 0 | 0 | 0 |

15(‘0’) | 1 | 9 | 36 | 55 | 42 | 78 | 69 | 42 | 12 | 18 | 9 | 3 | 0 | 0 | 0 | 0 | 0 |

16(‘0’) | 1 | 10 | 45 | 55 | 42 | 120 | 147 | 42 | 12 | 30 | 27 | 3 | 0 | 0 | 0 | 0 | 0 |

17(‘1’) | 1 | 10 | 45 | 100 | 97 | 120 | 147 | 189 | 54 | 30 | 27 | 30 | 3 | 0 | 0 | 0 | 0 |

Answer = f(17,4)+f(17,8)+f(17,12)+f(17,16) = 97 + 54 + 3 + 0 = **154**