2930. 重新排列后包含指定子字符串的字符串数目 (opens new window)

1.动规

定义dp[i][j][k][l]：表示前0~ i 个位置中，l出现个数为j，e出现次数为k，t出现次数为l的方法数。

对于第i个位置，l出现次数至少为1的方法数，包含两部分：

• 在第i个位置填入23个字母：前i-1字符串，已经满足字母 l 出现字数至少为1的方法数 x 23
• 在第i个位置填入字母l：前i-1字符串，满足字母 l 出现字数为0的方法数

字母l出现此处超出1的情况算入到出现次数恰好为1的情况。

✨与常规dp写法不同，这里是利用“当前子问题”的结果去更新”后面可能出现的子问题“的答案。

class Solution {
    public int stringCount(int n) {
        long[][][][] dp = new long[n][2][3][2];
        dp[0][0][0][0] = 23;
        dp[0][1][0][0] = 1;
        dp[0][0][1][0] = 1;
        dp[0][0][0][1] = 1;
        int mod = 1000000007;
        for (int i = 0; i < n-1; i++) {
            for (int j = 0; j < 2; j++) {
                for (int k = 0; k < 3; k++) {
                    for (int l = 0; l < 2; l++) {
                        dp[i + 1][j][k][l] = (dp[i + 1][j][k][l] + dp[i][j][k][l] * 23) % mod;
                        dp[i + 1][Math.min(j + 1, 1)][k][l] = (dp[i + 1][Math.min(j + 1, 1)][k][l] + dp[i][j][k][l]) % mod;
                        dp[i + 1][j][Math.min(k + 1, 2)][l] = (dp[i + 1][j][Math.min(k + 1, 2)][l] + dp[i][j][k][l]) % mod;
                        dp[i + 1][j][k][Math.min(l + 1, 1)] = (dp[i + 1][j][k][Math.min(l + 1, 1)] + dp[i][j][k][l]) % mod;
                    }
                }
            }
        }
        return (int)dp[n-1][1][2][1];
    }
}