0
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$ Apr 12, 2020 at 7:40

1 Answer 1

1
$\begingroup$

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.

$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.