题目描述

Alice 正在她的电脑上输入一个字符串。但是她打字技术比较笨拙，她 可能 在一个按键上按太久，导致一个字符被输入 多次。

给你一个字符串 word，它表示 最终 显示在 Alice 显示屏上的结果。同时给你一个 正 整数 k，表示一开始 Alice 输入字符串的长度 至少 为 k。

请你返回 Alice 一开始可能想要输入字符串的总方案数。

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

样例

输出：5

解释：

可能的字符串包括："aabbccdd"，"aabbccd"，"aabbcdd"，"aabccdd" 和 "abbccdd"。

输入：word = "aabbccdd", k = 8

输出：1

解释：

唯一可能的字符串是 "aabbccdd"。

输入：word = "aaabbb", k = 3

输出：8

限制

• 1 <= word.length <= 5 * 10^5
• word 只包含小写英文字母。
• 1 <= k <= 2000

算法

(背包动态规划) $O(n + k^2)$

1. 考虑长度最多为 $k-1$ 的方案数，然后通过总方案数减去这个方案数得到答案。
2. 将字符串按照连续字符进行分组。总方案数就是每组长度的乘积（乘法原理）。如果组数大于等于 $k$，则答案就是总方案数。
3. 设状态 $f(i, j)$ 表示前 $i$ 组，组成长度为 $j$ 的方案数。
4. 初始时，$f(0, 0) = 1$，其余为 $0$。
5. 转移时，对于一个长度为 $x$ 的组，转移 $f(i, j) = f(i - 1, j - 1) + f(i - 1, j - 2) + \dots + f(i - 1, j - x)$。注意到转移是一段区间的和，故可以采用前缀和的方式优化转移，即定义 $s(i, j) = s(i, j - 1) + f(i, j)$。
6. 最终答案为 $s(m, k - 1)$，这里 $m$ 是组数，不超过 $k$。

时间复杂度

• 预处理组的时间复杂度为 $O(n)$。
• 动态规划的状态数为 $O(k^2)$，转移时间为常数。
• 故总时间复杂度为 $O(n + k^2)$。

空间复杂度

• 注意到每次转移都只与前一维有关，故可以优化掉第一维的空间，优化后的空间复杂度为 $O(n + k)$。

C++ 代码

#define LL long long

class Solution {
public:
    int possibleStringCount(string word, int k) {
        const int n = word.size();
        if (n < k)
            return 0;

        const int mod = 1000000007;

        vector<int> cnt;
        int ans = 1;

        for (int i = 1, j = 0; i <= n; i++) {
            if (i < n && word[i] == word[j])
                continue;

            ans = (LL)(i - j) * ans % mod;
            cnt.push_back(i - j);
            j = i;
        }

        if (cnt.size() >= k)
            return ans;

        vector<int> f(k, 0), s(k, 0);
        f[0] = 1;
        for (int j = 0; j < k; j++)
            s[j] = 1;

        for (int x : cnt) {
            f[0] = 0;
            for (int j = 1; j < k; j++)
                f[j] = (s[j - 1] - (j - x - 1 >= 0 ? s[j - x - 1] : 0)) % mod;

            s[0] = f[0];
            for (int j = 1; j < k; j++)
                s[j] = (s[j - 1] + f[j]) % mod;
        }

        ans = ((ans - s[k - 1]) % mod + mod) % mod;

        return ans;
    }
};