3333. Find the Original Typed String II Hard

1/**
2 * [3333] Find the Original Typed String II
3 *
4 * 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.
5 * You are given a string word, which represents the final output displayed on Alice's screen. You are also given a positive integer k.
6 * 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.
7 * Since the answer may be very large, return it modulo 10^9 + 7.
8 *  
9 * <strong class="example">Example 1:
10 * <div class="example-block">
11 * Input: <span class="example-io">word = "aabbccdd", k = 7</span>
12 * Output: <span class="example-io">5</span>
13 * Explanation:
14 * The possible strings are: "aabbccdd", "aabbccd", "aabbcdd", "aabccdd", and "abbccdd".
15 * </div>
16 * <strong class="example">Example 2:
17 * <div class="example-block">
18 * Input: <span class="example-io">word = "aabbccdd", k = 8</span>
19 * Output: <span class="example-io">1</span>
20 * Explanation:
21 * The only possible string is "aabbccdd".
22 * </div>
23 * <strong class="example">Example 3:
24 * <div class="example-block">
25 * Input: <span class="example-io">word = "aaabbb", k = 3</span>
26 * Output: <span class="example-io">8</span>
27 * </div>
28 *  
29 * Constraints:
30 * 
31 * 	1 <= word.length <= 5 * 10^5
32 * 	word consists only of lowercase English letters.
33 * 	1 <= k <= 2000
34 * 
35 */
36pub struct Solution {}
37
38// problem: https://leetcode.com/problems/find-the-original-typed-string-ii/
39// discuss: https://leetcode.com/problems/find-the-original-typed-string-ii/discuss/?currentPage=1&orderBy=most_votes&query=
40
41// submission codes start here
42
43impl Solution {
44    pub fn possible_string_count(word: String, k: i32) -> i32 {
45        0
46    }
47}
48
49// submission codes end
50
51#[cfg(test)]
52mod tests {
53    use super::*;
54
55    #[test]
56    fn test_3333() {
57    }
58}
59