Find the Original Typed String II

Hard

#2960Time: 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()`.

Patterns

Dynamic Programming Prefix Sum

Data structures

String

Prompt

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⁹ + 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 * 10⁵
word consists only of lowercase English letters.
1 <= k <= 2000

Approaches

3 approaches with complexity analysis and trade-offs.

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.

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).

Walkthrough

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.

1class Solution {2    List<Integer> groups = new ArrayList<>();3    int k;4    long MOD = 1_000_000_007;5 6    public int numberOfWays(String word, int k) {7        this.k = k;8        if (word.length() == 0) {9            return 0;10        }11 12        for (int i = 0; i < word.length(); ) {13            char c = word.charAt(i);14            int j = i;15            while (j < word.length() && word.charAt(j) == c) {16                j++;17            }18            groups.add(j - i);19            i = j;20        }21 22        return (int) solve(0, 0);23    }24 25    private long solve(int index, int currentLength) {26        if (index == groups.size()) {27            return currentLength >= k ? 1 : 0;28        }29 30        long count = 0;31        int groupSize = groups.get(index);32        for (int i = 1; i <= groupSize; i++) {33            count = (count + solve(index + 1, currentLength + i)) % MOD;34        }35        return count;36    }37}

Complexity

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()`.

Trade-offs

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.

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.

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.

Walkthrough

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.

1class Solution {2    public int numberOfWays(String word, int k) {3        long MOD = 1_000_000_007;4        List<Integer> groups = new ArrayList<>();5        for (int i = 0; i < word.length(); ) {6            char c = word.charAt(i);7            int j = i;8            while (j < word.length() && word.charAt(j) == c) {9                j++;10            }11            groups.add(j - i);12            i = j;13        }14 15        int m = groups.size();16        long[] dp = new long[k];17        dp[0] = 1; // Base case: 0 groups, sum 0, 1 way18 19        for (int groupSize : groups) {20            long[] newDp = new long[k];21            long[] prefixSum = new long[k];22            prefixSum[0] = dp[0];23            for (int j = 1; j < k; j++) {24                prefixSum[j] = (prefixSum[j - 1] + dp[j]) % MOD;25            }26 27            for (int j = 1; j < k; j++) {28                long upper = prefixSum[j - 1];29                long lower = (j - 1 - groupSize >= 0) ? prefixSum[j - 1 - groupSize] : 0;30                newDp[j] = (upper - lower + MOD) % MOD;31            }32            dp = newDp;33        }34 35        long invalidWays = 0;36        for (long count : dp) {37            invalidWays = (invalidWays + count) % MOD;38        }39 40        long totalWays = 1;41        for (int groupSize : groups) {42            totalWays = (totalWays * groupSize) % MOD;43        }44 45        return (int) ((totalWays - invalidWays + MOD) % MOD);46    }47}

Complexity

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.

Trade-offs

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.

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.

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).

Walkthrough

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.

1class Solution {2    public int numberOfWays(String word, int k) {3        long MOD = 1_000_000_007;4        List<Integer> groups = new ArrayList<>();5        for (int i = 0; i < word.length(); ) {6            char c = word.charAt(i);7            int j = i;8            while (j < word.length() && word.charAt(j) == c) {9                j++;10            }11            groups.add(j - i);12            i = j;13        }14 15        int m = groups.size();16        long totalWays = 1;17        for (int groupSize : groups) {18            totalWays = (totalWays * groupSize) % MOD;19        }20 21        if (m >= k) {22            return (int) totalWays;23        }24 25        // Case m < k: Use DP to find invalid ways (sum < k)26        long[] dp = new long[k];27        dp[0] = 1; // Base case: 0 groups, sum 0, 1 way28 29        for (int groupSize : groups) {30            long[] newDp = new long[k];31            long[] prefixSum = new long[k];32            prefixSum[0] = dp[0];33            for (int j = 1; j < k; j++) {34                prefixSum[j] = (prefixSum[j - 1] + dp[j]) % MOD;35            }36 37            for (int j = 1; j < k; j++) {38                long upper = prefixSum[j - 1];39                long lower = (j - 1 - groupSize >= 0) ? prefixSum[j - 1 - groupSize] : 0;40                newDp[j] = (upper - lower + MOD) % MOD;41            }42            dp = newDp;43        }44 45        long invalidWays = 0;46        for (long count : dp) {47            invalidWays = (invalidWays + count) % MOD;48        }49 50        return (int) ((totalWays - invalidWays + MOD) % MOD);51    }52}

Complexity

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.

Trade-offs

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.

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem