3618 Find The Original Typed String Ii
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.
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
2
3
1 <= word.length <= 5 * 105
word consists only of lowercase English letters.
1 <= k <= 2000
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
class Solution:
def possibleStringCount(self, word: str, k: int) -> int:
mod = 10**9 + 7
n, cnt = len(word), 1
freq = list()
for i in range(1, n):
if word[i] == word[i - 1]:
cnt += 1
else:
freq.append(cnt)
cnt = 1
freq.append(cnt)
ans = 1
for o in freq:
ans = ans * o % mod
if len(freq) >= k:
return ans
f, g = [1] + [0] * (k - 1), [1] * k
for i in range(len(freq)):
f_new = [0] * k
for j in range(1, k):
f_new[j] = g[j - 1]
if j - freq[i] - 1 >= 0:
f_new[j] = (f_new[j] - g[j - freq[i] - 1]) % mod
g_new = [f_new[0]] + [0] * (k - 1)
for j in range(1, k):
g_new[j] = (g_new[j - 1] + f_new[j]) % mod
f, g = f_new, g_new
return (ans - g[k - 1]) % mod