Description
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.
Example 1:
Input: word = "aabbccdd", k = 7
Output: 5
Explanation:
The possible strings are: "aabbccdd", "aabbccd", "aabbcdd", "aabccdd", and "abbccdd".
Example 2:
Input: word = "aabbccdd", k = 8
Output: 1
Explanation:
The only possible string is "aabbccdd".
Example 3:
Input: word = "aaabbb", k = 3
Output: 8
Constraints:
1 <= word.length <= 5 * 105wordconsists only of lowercase English letters.1 <= k <= 2000
Solution
C++
class Solution {
public:
vector<long long> buildFreqArray(string& word) {
vector<long long> freq;
int n = word.size(), i = 0;
while (i < n) {
i++;
int f = 1;
while ((i < n) && (word[i] == word[i - 1]))
i++, f++;
freq.push_back(f);
}
return freq;
}
int findTotal(vector<long long>& freq, long long mod) {
long long ans = 1;
for (auto f : freq) {
ans = (ans * f) % mod;
}
return ans;
}
int possibleStringCount(string word, int k) {
int n = word.size(), mod = 1e9 + 7, ans = 0;
if (n <= k)
return n == k;
vector<long long> freq = buildFreqArray(word);
int total = findTotal(freq, mod);
int m = freq.size();
if (m >= k)
return total;
vector<vector<int>> dp(2, vector<int>(k, 0));
dp[m&1][0] = 1;
vector<int> prefix(k, 1);
for (int idx = m - 1; idx >= 0; idx--) {
dp[idx & 1][0] = 0;
vector<int> temp(k, 0);
for (int K = 1; K < k; K++) {
int res = (prefix[K - 1] - ((K - freq[idx] > 0) ? prefix[K - freq[idx] - 1] : 0) + mod) % mod;
temp[K] += res;
dp[idx&1][K] = res;
}
for (int i = 1; i < k; i++)
temp[i] = (temp[i] + temp[i - 1]) % mod;
prefix = temp;
}
for (int i = 1; i < k; i++)
{
ans = (ans + dp[0][i]) % mod;
};
return (total - ans + mod) % mod;
}
};