Find All Good Strings - Leetcode Solution

Problem Statement:

A string is called good if it satisfies the following conditions:

It contains only lowercase English letters. Its length is exactly $n$. It does not contain any of the substrings $abc$, $def$, or $ghi$. (i.e., it does not contain $abc$, $def$, or $ghi$ as a substring anywhere within the string). Given an integer $n$, return the number of good strings of length $n$. Since the answer may be large, return it modulo $10^9 + 7$.

Solution:

To solve this problem, we can use dynamic programming. We can define a state $dp[i][j]$ that represents the number of good strings of length $i$ that end with the character $j$ (where $j$ ranges from $a$ to $z$).

To compute the value of $dp[i][j]$, we can consider the last two characters of the string. If these characters form a forbidden substring ($ab$, $bc$, $de$, $ef$, $gh$, or $hi$), then the string cannot be good, and the value of $dp[i][j]$ should be 0. Otherwise, we can append the character $j$ to any good string of length $i-1$ that ends with a character that is not forbidden after appending $j$. Therefore, we can compute the value of $dp[i][j]$ as follows:

$$ dp[i][j]=\sum_{k=0}^{25}[forbidden(j,k)=0]dp[i-1][k] \quad (1) $$

where $forbidden(j,k)$ is a function that takes two characters $j$ and $k$ as input and returns $1$ if the substring formed by concatenating $j$ and $k$ is forbidden and $0$ otherwise. We can define the function $forbidden(j,k)$ as follows:

$$ forbidden(j,k)= \begin{cases} 1 &\text{if }(j,k)\in{(a,b),(b,c),(d,e),(e,f),(g,h),(h,i)}\ 0 &\text{otherwise} \end{cases} $$

Finally, the total number of good strings of length $n$ is the sum of $dp[n][j]$ for all characters $j$ from $a$ to $z$:

$$ \sum_{j=a}^{z}dp[n][j] \quad (2) $$

Now, we can implement the above algorithm using a 2D array to store the values of $dp$ and a nested loop to compute the values iteratively. We also need to initialize the base cases $dp[1][j]=1$ for all characters $j$ from $a$ to $z$, since there is only one string of length 1 that ends with each character.

The time complexity of this algorithm is $O(n)$ per state, and there are $26n$ states in total, so the overall time complexity is $O(n^2)$. The space complexity is also $O(n^2)$.

Here is the Python code for the above algorithm:

class Solution:
    def countGoodStrings(self, n: int) -> int:
        MOD = 10 ** 9 + 7
        dp = [[0] * 26 for _ in range(n + 1)]
        for i in range(26):
            dp[1][i] = 1
        for i in range(2, n + 1):
            for j in range(26):
                for k in range(26):
                    if not self.forbidden(chr(97+j), chr(97+k)):
                        dp[i][j] = (dp[i][j] + dp[i-1][k]) % MOD
        ans = sum(dp[n]) % MOD
        return ans
        
    def forbidden(self, j, k):
        return (j, k) in [('a', 'b'), ('b', 'c'), ('d', 'e'), ('e', 'f'), ('g', 'h'), ('h', 'i')]

The function countGoodStrings takes an integer n as input and returns the number of good strings of length n modulo $10^9 + 7$. The function first initializes the array dp with the base case values and then iteratively computes the values of $dp$ using equation $(1)$. Finally, the function computes the total number of good strings using equation $(2)$ and returns it.

The function forbidden takes two characters j and k as input and returns True if the substring formed by concatenating j and k is forbidden and False otherwise. The function uses a pre-defined list of forbidden substrings to check whether j and k form a forbidden substring.

1