重新排列后包含指定子字符串的字符串数目

题目

100126. 重新排列后包含指定子字符串的字符串数目

---

给你一个整数 n 。

如果一个字符串 s 只包含小写英文字母，且 将 s 的字符重新排列后，新字符串包含 子字符串 "leet" ，那么我们称字符串 s 是一个 好 字符串。

比方说：

• 字符串 "lteer" 是好字符串，因为重新排列后可以得到 "leetr" 。
• "letl" 不是好字符串，因为无法重新排列并得到子字符串 "leet" 。

请你返回长度为 n 的好字符串 总 数目。

由于答案可能很大，将答案对 10^9 + 7 取余 后返回。

子字符串 是一个字符串中一段连续的字符序列。

示例 1：

输入：n = 4
输出：12
解释：总共有 12 个字符串重新排列后包含子字符串 "leet" ："eelt" ，"eetl" ，"elet" ，"elte" ，"etel" ，"etle" ，"leet" ，"lete" ，"ltee" ，"teel" ，"tele" 和 "tlee" 。

示例 2：

输入：n = 10
输出：83943898
解释：长度为 10 的字符串重新排列后包含子字符串 "leet" 的方案数为 526083947580 。所以答案为 526083947580 % (109 + 7) = 83943898 。

提示：

• 1 <= n <= 10^5

题解

方法一：

思路

动态规划

设$dp_{i,j,k,l}$为前i个字符中，已经选了至少j个l，选了至少k个t，选了至少l个e，的方案数。这是三种费用的至少型01背包。

$dp_{i,j,k,l} = 23 dp_{i-1,j,k,l} + dp_{i-1, j’, k, l} + dp_{i-1, j, k’, l} + dp_{i-1, j, k, l’}$

$j’= max(0,j-1), k’= max(0,k-1), l’= max(0,l-1)$

代码

class Solution {
public:
    using ll = long long;
    const ll MOD = 1e9+7;
    int stringCount(int n) {
        ll dp[n+1][2][2][3];
        memset(dp, 0, sizeof(dp));
        dp[0][0][0][0] = 1;
        for (int i=1; i<=n; i++) {
            for (int a=0; a<2; a++) {
                for (int b=0; b<2; b++) {
                    for (int c=0; c<3; c++) {
                        dp[i][a][b][c] = dp[i-1][a][b][c]*23%MOD
                        + dp[i-1][max(a-1, 0)][b][c]
                        + dp[i-1][a][max(b-1, 0)][c]
                        + dp[i-1][a][b][max(c-1, 0)];
                        dp[i][a][b][c] %= MOD;
                    }
                }
            }
        }
        return dp[n][1][1][2];
    }
};

方法二：

思路

先求出总的方案数$26^n$，然后考虑移除不合法的个数。

不合法有三种条件。

设$A$为没有一个l的情况；设$B$为没有一个t的情况；设$C$为没有一个e或只有一个e的情况。

设$P(i)$为情况$i$的方案数。

根据容斥原理，不合法的方案数为$P(A)+P(B)+P(C)-P(A\cap B) - P(B\cap C) - P(B\cap C) + P(A\cap B \cap C)$

代码

class Solution {
public:
    using ll = long long;
    const ll MOD = 1e9+7;
    ll fpow(ll x, int p) {
        ll rt = 1;
        while (p) {
            if (p&1) rt *= x, rt %= MOD;
            x = x*x;
            x %= MOD;
            p >>= 1;
        }
        return rt;
    }
    int stringCount(int n) {
        ll ans = fpow(26, n);
        ans = (ans - (3*fpow(25, n)%MOD+n*fpow(25,n-1))%MOD + MOD) % MOD;
        ans = (ans + (3*fpow(24, n)%MOD+2*n*fpow(24,n-1))%MOD) % MOD;
        ans = (ans - (fpow(23, n)%MOD+n*fpow(23,n-1))%MOD + MOD) % MOD;
        return ans;
    }
};