3333. Find the Original Typed String II

Alice is attempting to type a specific string on her computer. However, she tends to be clumsy and may press a key for too long, resulting in a character being typed multiple times.

You are given a string word, which represents the final output displayed on Alice’s screen. You are also given a positive integer k.

Return the total number of possible original strings that Alice might have intended to type, if she was trying to type a string of size at least k.

Since the answer may be very large, return it modulo 109 + 7.

class Solution {
public:
    int possibleStringCount(string word, int k) {
        long long mod = 1e9 + 7, res = 0;
        word.push_back('#');
        vector<long long> buc;
        for(int i = 1, cnt = 1; i < word.length(); i++) {
            if(word[i] == word[i-1]) cnt++;
            else {
                buc.push_back(cnt);
                cnt = 1;
            }
        }
        vector<long long> suf(buc.size(), buc.back());
        for(int i = buc.size() - 2; i >= 0; i--) {
            suf[i] = suf[i+1] * buc[i] % mod;
        }
        if(buc.size() >= k) return suf[0];
        vector<long long> dp(k+1);
        dp[0] = 1;
        for(int i = 0; i < buc.size(); i++) {
            res = (res + dp[k] * suf[i] % mod) % mod;
            vector<long long> dpp(k+1);
            for(int j = 0; j < k; j++) {
                dpp[j+1] = (dpp[j+1] + dp[j]) % mod;
                long long until = j + buc[i];
                if(until <= k) {
                    if(until < k) dpp[until+1] = (dpp[until+1] - dp[j] + mod) % mod;
                } else {
                    long long cnt = until - k;
                    dpp[k] = (dpp[k] + cnt * dp[j] % mod) % mod;
                }
            }
            for(int j = 1; j < dpp.size(); j++) dpp[j] = (dpp[j] + dpp[j-1]) % mod;
            swap(dp,dpp);
        }
        return (res + dp[k]) % mod;
    }
};