找到初始输入字符串Ⅱ

#include <iostream>
#include <vector>

using namespace std;

class Solution {
public:
    int possibleStringCount(string word, int k) {
        int n = word.size(), mod = 1e9+7;
        vector<int> x;
        //  分组:
        //  假定输入字符串 word = "aaabb", k = 3
        //  首先,把它拆成连续相同字符的块:word = "aaa" | "bb"，
        //  所以块长度数组 x = [3, 2]，总块数 m = 2
        for (int i=0, cnt=1; i<n; i++) {
            if (i+1<n && word[i]==word[i+1]) cnt++;
            else { x.push_back(cnt); cnt=1; }
        }
        //  每个相同字符块内,你可以截取任意长度 l (1 ≤ l ≤ xᵢ)作为最终保留。
        //  块与块之间互不影响，总方案数就是各块方案数的乘积：
        //  块 1（长度 3）：可选长 1、2、3 → 3 种
        //  块 2（长度 2）：可选长 1、2 → 2 种
        //  于是 total = 3 × 2 = 6(ab, aab, aaab, abb, aabb, aaabb).
        long long total = 1;
        for (int len : x)
            total = total * len % mod;
        // 当字符串块数 m 大于等于 k 时,直接返回 total.
        // 当字符串块数 m 小于 k 时，说明有些方案会导致字符块长度不足 k，需要剪除它们.
        int m = x.size();
        if (m >= k) return total;           
        // 使用动态规划与前缀和的方法剪除字符块长度不足 k 的情况，没看懂
        // dp[i][j] 表示 前 i 个原始块，恰好截取后构成 j 个块的方案数.
        // 令 dp[0][0] = 1(还没处理任何块时，截成 0 块只有一种“空”方案).
        vector<vector<int>> dp(m+1, vector<int>(k));
        dp[0][0] = 1;
        for (int i=0; i<m; i++) {
            vector<int> S(k+1);
            for (int j=0; j<k; j++)
                S[j+1] = (S[j] + dp[i][j]) % mod;
            for (int j=0; j<k; j++) {
                int left = max(0, j - x[i]);
                dp[i+1][j] = (S[j] - S[left] + mod) % mod;
            }
        }
        long long bad = 0;
        for (int j=0; j<k; j++)
            bad = (bad + dp[m][j]) % mod;

        return (total - bad + mod) % mod;
    }
};

int main() {
    Solution solution;
    int result = solution.possibleStringCount("aaabb", 3);
    std::cout << result << std::endl;
}