Finding total valid strings of length N that could be formed using characters A,B and C which satisfies given criteria 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.
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:


It should have $\le c$ number of C's
At most $a$ of its ending characters are A
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 &gt; 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 &gt; 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.