# 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.

• Construct a DFA (our unambiguous NFA) for the language, and use the transfer method technique. There are several answers on this site with examples of this method. Apr 12, 2020 at 7:40

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.