Two letter strings are the strings consisting of only two letters "X" and "Y". A string is "super two letter string" if
a) It does not have leading "X" letters. b) It does not contain P consecutive "X" letters. Your task is to find total number of Super two letter strings of length N.
How to identify the states of dynamic programming for the above problem? Problem Link: Super two letter strings
Thanks!
let ind : the current index we are in at this state
let con : number of consecutive "X" characters we had in our state
let f(ind, con) be our answer
of-course we will put "Y" in index 1
f(ind, con >= p) = 0
f(N, con) = 1 + (con < p — 1)
f(ind, con) = f(ind + 1, con + 1) + f(ind + 1, 0)
our answer would be f(2, 0)
also don't forget to mod after each operation
UPD : updated the basecases
Consider the process of creating the sequence. There are many ways to define states however you like. Here is one way: Let cnt(N) be the number of string with the properties mentioned above. The recurence looks as follows:
cnt(N) = cnt(N - 1) + cnt(N - 2) + ... + cnt(N - P)
Why so you may ask. First we consider that we place and Y on position N, then we just need to consider cnt(N - 1)-the strings of length N - 1. Now consider placing a continuous seqence of X of length L = 1, 2, ..., P - 1. We place a sequence of length L on position N, so we are left with a string of length N - L. Now we place an Y on position N - L and we add to cnt(N) the value of cnt(N - L - 1), of course only if N - L - 1 ≥ 0.
Why is this correct? Because in this way we "cover" the set of all possible solutions by considering such a construction process. I like to view this as a bijection from the set of all possible strings that hold a certain property to the set of all possible constructions.(each string from the set of solution has an unique representation with the operations we used in the recurence above)
Can you please explain what is happening in this solution (Link)?