Find the Original Typed String II - Solution & Explanation
Problem Statement
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 * 105wordconsists only of lowercase English letters.1 <= k <= 2000
Approach Overview
Problem Overview: You are given a typed string where characters may appear multiple times because of long key presses. Each group of identical characters could represent fewer presses in the original string. The task is to count how many possible original strings could produce the typed result while satisfying a minimum length constraint k.
Approach 1: Dynamic Programming with Prefix Sum Optimization (O(m · k) time, O(k) space)
Start by compressing the typed string into groups of consecutive characters. For example, aaabb becomes counts [3,2]. If a group has length g, the original string could contain between 1 and g copies of that character. Let dp[j] represent the number of ways to build an original string of length j using processed groups. For each group, transition by adding between 1 and g characters. Direct transitions would be expensive, so prefix sums are used to compute range sums efficiently when updating the DP array.
The key observation: the total combinations from all groups is simply the product of their sizes, but some produce strings shorter than k. The DP tracks counts for lengths < k. Subtract these from the total combinations to get the number of valid originals with length at least k. This approach combines dynamic programming with prefix sum range aggregation to keep updates efficient.
Approach 2: Suffix Array Technique (O(n log n) time, O(n) space)
A suffix-array-based method analyzes repeated character structure directly from the string. By constructing a suffix array and LCP (Longest Common Prefix) array, you can efficiently detect stretches where characters repeat and reason about how many valid contractions of the typed string are possible. These repeated segments correspond to the same groups used in the DP solution. Once the repetition boundaries are identified, you compute the number of valid reductions per segment and combine them while enforcing the minimum length constraint.
This technique relies heavily on advanced string processing structures such as suffix arrays and LCP arrays. It is more implementation-heavy but performs well when working with large strings or when repetition structure must be extracted efficiently from raw text.
Recommended for interviews: The dynamic programming solution with prefix sums is the expected approach. It demonstrates strong reasoning about combinatorics and efficient DP transitions. A brute-force enumeration of all possible contractions quickly becomes exponential, so showing the DP formulation and prefix-sum optimization signals solid algorithmic maturity.
Approach 1: Dynamic Programming Approach
In this approach, we use dynamic programming to calculate the number of possible original strings Alice intended to type. We will focus on the concept of reducing consecutive duplicate characters in different ways while maintaining a valid length. We'll employ a DP table where each entry represents the number of ways to achieve a certain length of the original string from the current character.
This solution uses a dynamic programming technique, where dp[i] represents the number of ways to transform the substring starting at index i into valid original strings. We iterate over the word from back to front, updating the dp array based on whether characters can be combined. We then sum the dp values from k to n (inclusive) to get the total possible strings of at least length k.
Code
Python
JavaScript
Complexity
Time Complexity: O(n), where n is the length of the word. We traverse the string linearly.
Space Complexity: O(n), due to the additional storage used for the dp array.
Approach 2: Suffix Array Technique
This approach leverages suffix arrays to handle large scale string operations efficiently. The key idea is creating suffix arrays to help quickly calculate the possible original string counts using combinations from the given string `word`. However, given the constraints, this method may be less efficient compared to dynamic programming for this problem size.
This C solution utilizes a suffix array-like approach with dynamic decisions. It fills a dp array from the end of the string to the beginning, deciding at each step whether to merge consecutive duplicate letters and how it affects potential valid original strings. The final result is the sum of dp values from index k onward, considering modulus arithmetic for large numbers.
Complexity
Time Complexity: O(n), iterating over the string.
Space Complexity: O(n), for the dp array storage.
Approach 3: Dynamic Programming + Prefix Sum
For the constraint that the length is at least k, we can split it into two subproblems:
- Without length restriction, for each group of consecutive identical characters, we can choose any number from
1to the length of the group. Let the number of ways bea. - For length less than
k, let the number of ways beb.
Thus, the final answer is a - b.
We can group consecutive identical characters in the string word. Since at least one character must be chosen from each group, if a group has more than 0 remaining selectable characters, we add it to an array nums. After initially selecting one character from each group, we update the remaining required character count k.
If k < 1, it means that after selecting one character from each group, the requirement of length at least k is already satisfied, so the answer is a.
Otherwise, we need to calculate the value of b. We use a 2D array f, where f[i][j] represents the number of ways to select j characters from the first i groups. Initially, f[0][0] = 1, meaning there is 1 way to select 0 characters from 0 groups. Then b = sum_{j=0}^{k-1} f[m][j], where m is the length of nums. The answer is a - b.
Consider the transition equation for f[i][j]. For the i-th group of characters, suppose its remaining length is x. For each j, we can enumerate the number of characters l chosen from this group, where l \in [0, min(x, j)]. Then, f[i][j] can be transferred from f[i-1][j-l]. We can use prefix sums to optimize this transition.
The time complexity is O(n + k^2), and the space complexity is O(k^2), where n is the length of the string word.
Code
Python
Java
C++
Go
TypeScript
Complexity Comparison
| Approach | Complexity |
|---|---|
| Dynamic Programming Approach | Time Complexity: O(n), where n is the length of the word. We traverse the string linearly. |
| Suffix Array Technique | Time Complexity: O(n), iterating over the string. |
| Dynamic Programming + Prefix Sum | — |
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Dynamic Programming + Prefix Sum | O(m · k) | O(k) | Best general solution when counting valid original lengths with a constraint |
| Suffix Array Technique | O(n log n) | O(n) | Useful when analyzing repetition structure in very large strings |
Video Solution
Find the Original Typed String II | Multiple Approaches | Detailed | Leetcode 3333 |codestorywithMIK • codestorywithMIK • 16,134 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Find the Original Typed String II easy or hard?
Find the Original Typed String II Python/Java solution
How to solve Find the Original Typed String II in O(n)?
What is the best approach for Find the Original Typed String II?
Is Find the Original Typed String II asked at Google/Amazon/Meta?
What data structure is used in Find the Original Typed String II?
What is the time complexity of Find the Original Typed String II?
Ready to solve this problem?
Practice Find the Original Typed String II with our built-in code editor and test cases.
Practice on FleetCode