Find the number of ternary strings (using A,B,C,D) of length n such that it doesn’t contain the substring “AA”. Just the recurrence relation…
Find the number of ternary strings (using A,B,C,D) of length n such that it doesn’t contain the substring “AB”. Just the recurrence relation…
I just wanted to know how the first question’s approach is different from the second’s question…
Hey, the approach will be similar. We can keep two states in the DP: index of the string (where we are deciding to put A,B,C or D) and length_matched - i.e. uptil what index of “AA” or “AB” we have already matched (this can be 0 or 1 atmost). Now we can check while putting any A,B,C,D that we are not matching the entire string, and also update the length_matched accordingly. Note that for “AA” or “AB” its this easy, for other bigger strings, you might have to use KMP failure function to decide what will be the new length_matched after adding a character c.