Finding total valid strings of length N that could be formed using characters A,B and C which satisfies given criteria

Question

You have to find out the number of good strings of length N characters in size which you can make using characters A B and C.

A string is a good String if it satisfies the following three criteria:

• The total number of C in the string should not be greater than equal to 4.
• There should not be more than two consecutive A's in the string.
• Any two B's should be at least two characters apart.

How do I find total possible good strings for N length string?

Any psudo code will really help. Thank you.

Answer 1

Let $0 \leq i \leq n, 0 \leq c \leq 3, 0 \leq a \leq 2, 0 \leq b \leq 2$, and $DP[i][c][a][b]$, denote the number of good strings of length $i$, but which also have more restrictions:

1. It should have $\le c$ number of C's

2. At most $a$ of its ending characters are A

3. None of the last $b$ characters are B.

The final answer that we are looking for is $DP[n][3][2][0]$. Note that having 2 in the third parameter adds nothing extra over the restriction that the string already be a good string. Similarly, the fourth parameter being 0 also adds no further restrictions.

To compute $DP[i][c][a][b]$, we look at the possibilities of the last character:

If $c > 0$, then the last character can be C, and the term that would be added is $DP[i-1][c-1][2][\text{max}\{0, b-1\}]$.

If $a > 0$, then the last character can be A, and the term that would be added is $DP[i-1][c][a-1][\text{max}\{0, b-1\}]$.

If $b = 0$, then the last character can be B, and the term that would be added is $DP[i-1][c][2][2]$.

The base case would be $DP[0][c][a][b] = 1$.

This Dynamic Programming can thus be solved in $\mathcal{O}(n)$ time and space.