# Find the Original Typed String II
**Difficulty:** HARD
[External](https://leetcode.com/problems/find-the-original-typed-string-ii)
Canonical: https://scaleengineer.com/dsa/problems/find-the-original-typed-string-ii
**Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming), [Prefix Sum](https://scaleengineer.com/dsa/patterns/prefix-sum)
**Data structures:** String
---
## Problem
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 * 105`
* `word` consists only of lowercase English letters.
* `1 <= k <= 2000`

# Approaches
## Brute-Force Recursion
A straightforward but inefficient approach is to use brute-force recursion. The idea is to explore every possible original string that could have produced the given `word`. We can define a recursive function that builds the original string group by group, keeping track of the current total length. When all groups have been processed, we check if the total length meets the `k` requirement.
**Time:** O(Π n_i), where `n_i` is the size of the i-th group. In the worst case, like `"aabbcc..."`, this is `O(2^(N/2))`, which is exponential and too slow. · **Space:** O(m), where `m` is the number of groups. This is for the recursion stack depth. In the worst case, `m` can be equal to `word.length()`.
**Pros:** Simple to understand and implement.; Correctly solves the problem for very small inputs.
**Cons:** Extremely inefficient due to redundant computations.; The time complexity is exponential in the number of groups, making it infeasible for the given constraints.; Will result in a 'Time Limit Exceeded' (TLE) error on most platforms.
### Explanation
This method systematically generates all possible original strings. We first preprocess the `word` to identify consecutive character groups and their counts. For instance, `"aaabbc"` has three groups: `a` with count 3, `b` with count 2, and `c` with count 1. An original string is formed by choosing a length `j_i` (from 1 to `n_i`) for each group `i`. A recursive function can explore these choices. The function would take the current group index and the accumulated length as parameters. It would iterate through all possible lengths for the current group and recursively call itself for the next group with an updated length. The recursion terminates when all groups are considered, at which point the total length is checked against `k`.

```java
class Solution {
    List<Integer> groups = new ArrayList<>();
    int k;
    long MOD = 1_000_000_007;

    public int numberOfWays(String word, int k) {
        this.k = k;
        if (word.length() == 0) {
            return 0;
        }

        for (int i = 0; i < word.length(); ) {
            char c = word.charAt(i);
            int j = i;
            while (j < word.length() && word.charAt(j) == c) {
                j++;
            }
            groups.add(j - i);
            i = j;
        }

        return (int) solve(0, 0);
    }

    private long solve(int index, int currentLength) {
        if (index == groups.size()) {
            return currentLength >= k ? 1 : 0;
        }

        long count = 0;
        int groupSize = groups.get(index);
        for (int i = 1; i <= groupSize; i++) {
            count = (count + solve(index + 1, currentLength + i)) % MOD;
        }
        return count;
    }
}
```
### Algorithm
- Parse the input `word` into a list of groups, where each group consists of a character and its consecutive count. For example, `"aaabbc"` becomes `[('a', 3), ('b', 2), ('c', 1)]`.
- Implement a recursive function, say `countWays(groupIndex, currentLength)`.
- **Base Case:** If `groupIndex` reaches the end of the list of groups, check if `currentLength >= k`. If it is, we have found one valid original string, so return 1. Otherwise, return 0.
- **Recursive Step:** For the current group `(character, count)` at `groupIndex`, iterate through all possible lengths `j` from 1 to `count`. For each `j`, make a recursive call `countWays(groupIndex + 1, currentLength + j)`. Sum up the results from these recursive calls.
- The initial call would be `countWays(0, 0)`.

## Dynamic Programming
The brute-force approach suffers from recomputing the same subproblems. We can use dynamic programming with memoization to store and reuse results. A more standard DP approach is to build a table iteratively. We can calculate the number of ways to form an original string with a specific length. A key insight is to count the complement: find the number of original strings with length *less than* `k` and subtract this from the total number of possible original strings.

The total number of original strings is the product of the sizes of all character groups. The number of strings with length less than `k` can be found using a DP table `dp[i][j]`, representing the number of ways to achieve a total length `j` using the first `i` groups. The transition involves summing up results from the previous state, which can be optimized from `O(n_i)` to `O(1)` per state using prefix sums.
**Time:** O(m*k), where `m` is the number of groups and `k` is the target length. This is because we iterate through `m` groups, and for each group, we do `O(k)` work to fill the new DP row. · **Space:** O(m*k) for the DP table. Can be optimized to O(k) by only storing the previous row's DP values.
**Pros:** Much more efficient than brute force.; Systematically builds the solution, avoiding redundant work.; The prefix sum optimization significantly improves performance.
**Cons:** The time complexity is proportional to the number of groups `m`.; If `m` is large (e.g., `m` is close to `word.length()`), this approach is still too slow and will TLE.
### Explanation
Let's define `dp[i][j]` as the number of ways to choose lengths for the first `i` groups such that their sum is exactly `j`. We are interested in `j < k`. The DP table will have dimensions `(m+1) x k`, where `m` is the number of groups.

The state transition is `dp[i][j] = Σ_{l=1 to n_i} dp[i-1][j-l]`, where `n_i` is the size of the `i`-th group. A naive implementation of this would take `O(n_i)` for each state, leading to a total time complexity of `O(m * k * n_avg) = O(N * k)`. We can optimize the summation. Notice that `Σ_{l=1 to n_i} dp[i-1][j-l]` is a sum over a contiguous range. By pre-calculating prefix sums for the `dp[i-1]` row, we can compute this sum in `O(1)`. Let `S[i-1][x] = Σ_{p=0 to x} dp[i-1][p]`. Then `dp[i][j] = S[i-1][j-1] - S[i-1][j-n_i-1]`. This reduces the complexity of each state transition to `O(1)`, and the total time to `O(m*k)`. We can also optimize space to `O(k)` by only keeping track of the previous DP row.

```java
class Solution {
    public int numberOfWays(String word, int k) {
        long MOD = 1_000_000_007;
        List<Integer> groups = new ArrayList<>();
        for (int i = 0; i < word.length(); ) {
            char c = word.charAt(i);
            int j = i;
            while (j < word.length() && word.charAt(j) == c) {
                j++;
            }
            groups.add(j - i);
            i = j;
        }

        int m = groups.size();
        long[] dp = new long[k];
        dp[0] = 1; // Base case: 0 groups, sum 0, 1 way

        for (int groupSize : groups) {
            long[] newDp = new long[k];
            long[] prefixSum = new long[k];
            prefixSum[0] = dp[0];
            for (int j = 1; j < k; j++) {
                prefixSum[j] = (prefixSum[j - 1] + dp[j]) % MOD;
            }

            for (int j = 1; j < k; j++) {
                long upper = prefixSum[j - 1];
                long lower = (j - 1 - groupSize >= 0) ? prefixSum[j - 1 - groupSize] : 0;
                newDp[j] = (upper - lower + MOD) % MOD;
            }
            dp = newDp;
        }

        long invalidWays = 0;
        for (long count : dp) {
            invalidWays = (invalidWays + count) % MOD;
        }

        long totalWays = 1;
        for (int groupSize : groups) {
            totalWays = (totalWays * groupSize) % MOD;
        }

        return (int) ((totalWays - invalidWays + MOD) % MOD);
    }
}
```
### Algorithm
- The problem asks for the number of ways to get a total length of at least `k`. It's easier to calculate the total number of ways and subtract the number of ways to get a length less than `k`.
- Total ways = `product(n_i)` for all groups `i`.
- To find ways for length `< k`, we use DP. Let `dp[i][j]` be the number of ways to get a total length of `j` using the first `i` groups.
- **State:** `dp[i][j]` = number of ways to get sum `j` using first `i` groups.
- **Base Case:** `dp[0][0] = 1` (0 groups, sum 0, 1 way).
- **Recurrence:** `dp[i][j] = Σ_{l=1 to n_i} dp[i-1][j-l]`.
- This can be optimized using prefix sums. Let `S[i-1]` be the prefix sum array for `dp[i-1]`. Then `dp[i][j] = S[i-1][j-1] - S[i-1][j-n_i-1]`.
- The final number of invalid ways is `Σ_{j=0 to k-1} dp[m][j]`.
- The answer is `(Total ways - Invalid ways) % MOD`.

## Optimized Dynamic Programming
This approach builds upon the previous DP solution by incorporating a critical observation about the problem constraints. The minimum length of any possible original string is equal to the number of character groups, `m`, since each group must contribute at least one character. This leads to a powerful optimization.

If `m >= k`, we know for sure that any original string will have a length of at least `k`. Thus, we don't need to perform any complex counting; all possible combinations are valid. The answer is simply the product of the sizes of all groups.

If `m < k`, we proceed with the DP approach described previously to count the number of 'invalid' strings (those with length `< k`). Since `m` is now bounded by `k`, the `O(m*k)` complexity becomes `O(k^2)`, which is efficient enough to pass within the time limits.
**Time:** O(N + min(m, k) * k). Since `m <= N`, this is effectively `O(N + k^2)`. `O(N)` for parsing, and if `m < k`, `O(m*k)` which is less than `O(k^2)` for the DP part. · **Space:** O(N + k). `O(N)` to store the group sizes in the worst case, and `O(k)` for the DP arrays.
**Pros:** Highly efficient and handles all constraints.; Combines a clever observation with dynamic programming.; The `m >= k` case provides a fast path that avoids complex calculations for a large set of inputs.
**Cons:** The logic is slightly more complex due to the case analysis.
### Explanation
The algorithm first determines the number of groups, `m`. 

If `m >= k`, the problem simplifies greatly. The shortest possible original string is formed by taking one character from each of the `m` groups, resulting in a length of `m`. Since `m >= k`, this shortest string already satisfies the condition. Any other choice will only result in a longer string, which also satisfies the condition. Hence, every single combination is valid. The total number of ways is `n_1 * n_2 * ... * n_m` (modulo `10^9 + 7`). This part takes `O(N)` to parse the string and `O(m)` to compute the product.

If `m < k`, we must filter out the combinations that result in a total length less than `k`. We use the space-optimized `O(m*k)` DP from the previous approach. We maintain a `dp` array of size `k`, where `dp[j]` stores the number of ways to get a total length of `j`. We iterate through each of the `m` groups, updating the `dp` array using prefix sums. Since we are in the case where `m < k`, the total time for this DP calculation is bounded by `O(k * k) = O(k^2)`. After processing all `m` groups, we sum up the values in the final `dp` array to get the total number of invalid ways. The final answer is `(Total Ways - Invalid Ways) % MOD`.

This case-based analysis ensures that we avoid the expensive `O(m*k)` computation when `m` is large, making the solution efficient for all valid inputs.

```java
class Solution {
    public int numberOfWays(String word, int k) {
        long MOD = 1_000_000_007;
        List<Integer> groups = new ArrayList<>();
        for (int i = 0; i < word.length(); ) {
            char c = word.charAt(i);
            int j = i;
            while (j < word.length() && word.charAt(j) == c) {
                j++;
            }
            groups.add(j - i);
            i = j;
        }

        int m = groups.size();
        long totalWays = 1;
        for (int groupSize : groups) {
            totalWays = (totalWays * groupSize) % MOD;
        }

        if (m >= k) {
            return (int) totalWays;
        }

        // Case m < k: Use DP to find invalid ways (sum < k)
        long[] dp = new long[k];
        dp[0] = 1; // Base case: 0 groups, sum 0, 1 way

        for (int groupSize : groups) {
            long[] newDp = new long[k];
            long[] prefixSum = new long[k];
            prefixSum[0] = dp[0];
            for (int j = 1; j < k; j++) {
                prefixSum[j] = (prefixSum[j - 1] + dp[j]) % MOD;
            }

            for (int j = 1; j < k; j++) {
                long upper = prefixSum[j - 1];
                long lower = (j - 1 - groupSize >= 0) ? prefixSum[j - 1 - groupSize] : 0;
                newDp[j] = (upper - lower + MOD) % MOD;
            }
            dp = newDp;
        }

        long invalidWays = 0;
        for (long count : dp) {
            invalidWays = (invalidWays + count) % MOD;
        }

        return (int) ((totalWays - invalidWays + MOD) % MOD);
    }
}
```
### Algorithm
- First, parse the `word` into a list of group lengths `n_1, n_2, ..., n_m`.
- **Crucial Observation:** The minimum possible length of an original string is `m`, achieved by choosing length 1 from each group. 
- **Case 1: `m >= k`**
  - If the number of groups `m` is greater than or equal to `k`, any possible original string will have a length of at least `m >= k`.
  - Therefore, all possible combinations are valid. The answer is the total number of combinations, which is the product of all group sizes: `Π n_i` (mod `10^9 + 7`).
- **Case 2: `m < k`**
  - In this case, some combinations might result in a total length less than `k`.
  - We use the same `O(m*k)` DP approach as in the previous method to count these invalid combinations.
  - Since `m < k`, the time complexity of the DP part becomes `O(m*k) < O(k^2)`.
- The overall complexity is dominated by parsing the string and the DP calculation, leading to `O(N + k^2)`.