3333. Find the Original Typed String II

Posted on Edited on In

3333. Find the Original Typed String II

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 10^9 + 7.

Example 1:

1
2
3
Input: word = "aabbccdd", k = 7

Output: 5

Explanation:

The possible strings are: "aabbccdd", "aabbccd", "aabbcdd", "aabccdd", and "abbccdd".

Example 2:

1
2
3
Input: word = "aabbccdd", k = 8

Output: 1

Explanation:

The only possible string is "aabbccdd".

Example 3:

1
2
3
Input: word = "aaabbb", k = 3

Output: 8

Constraints:

  • 1 <= word.length <= 5 * 10^5
  • word consists only of lowercase English letters.
  • 1 <= k <= 2000

Hints/Notes

Solution

Language: C++

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
39
40
41
42
43
44
45
46
47
48
49
class Solution {
public:
    // what we want to calculate here:
    // the number of strings with len < k
    // the meaning of dp[i][j]: when we are at ith index of len,
    // we have j digits left, how many such strings we can form
    int possibleStringCount(string word, int k) {
        vector<int> lens;
        int n = word.size(), MOD = 1e9 + 7;
        for (int i = 0; i < n;) {
            int c = word[i], left = i;
            while (i < n && word[i] == c) {
                i++;
            }
            lens.push_back(i - left);
        }
        int len = lens.size();
        long res = 1;
        if (len == k) {
            return res;
        }
        for (int i = 0; i < len; i++) {
            res = (res * lens[i]) % MOD;
        }
        vector<long> preSum(k + 1, 0);
        // the range of dp[i][j]:
        // i is index, [0, len]
        // j is the remaining length [0, k - 1]
        vector<vector<int>> dp(len + 1, vector<int>(k, -1));
        for (int i = 0; i < k; i++) {
            dp[len][i] = 1;
            preSum[i + 1] = (preSum[i] + 1) % MOD;
        }
        // maxI = min(lens[idx],rem - (len - idx - 1));
        // dp[i][j] = dp[i + 1][j - 1] + dp[i + 1][j - 2] + ... + dp[i + 1][j - maxI]
        // so if we have a preSum, it would be preSum[j - 1] - preSum[j - maxI - 1]
        for (int i = len - 1; i >= 0; i--) {
            for (int j = 0; j < k; j++) {
                int maxI = min(lens[i], j - (len - i - 1));
                int start = j - maxI;
                dp[i][j] = (preSum[j] - preSum[start] + MOD) % MOD;
            }
            for (int j = 0; j < k; j++) {
                preSum[j + 1] = (preSum[j] + dp[i][j]) % MOD;
            }
        }
        return (res - dp[0][k - 1] + MOD) % MOD;
    }
};

The recursive solution:

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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
class Solution {
public:
    // what we want to calculate here:
    // the number of strings with len < k
    // the meaning of dp[i][j]: when we are at kth index of len,
    // we have j digits left, how many such strings we can form
    vector<vector<int>> dp;
    vector<int> lens;
    int MOD = 1e9 + 7, len;

    int possibleStringCount(string word, int k) {
        dp.resize(k, vector<int>(k, -1));
        int n = word.size();
        for (int i = 0; i < n;) {
            int c = word[i], left = i;
            while (i < n && word[i] == c) {
                i++;
            }
            lens.push_back(i - left);
        }
        len = lens.size();
        long res = 1;
        for (int i = 0; i < len; i++) {
            res = (res * lens[i]) % MOD;
        }
        if (len >= k) {
            return res;
        }
        int less = dfs(0, k - 1);
        return (res - less + MOD) % MOD;
    }

    int dfs(int idx, int rem) {
        // it means we reached the end of the lens
        if (idx == len) {
            return 1;
        }
        // there needs at least one digit for one lens item
        if (len - idx > rem) {
            return 0;
        }
        if (dp[idx][rem] != -1) {
            return dp[idx][rem];
        }
        // now we are at lens[idx], how many number can we pick at this index?
        // if we pick at least one digit per index, then we will pick
        // lens.size() - index number
        // we can pick from 1 to rem - (lens.size() - index - 1)
        long long res = 0;
        for (int i = 1; i <= min(lens[idx],rem - (len - idx - 1)); i++) {
            res = (res + dfs(idx + 1, rem - i)) % MOD;
        }
        dp[idx][rem] = res;
        return res;1111111
    }
};