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.

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

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