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 * 105word consists only of lowercase English letters.1 <= k <= 2000In 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.
JavaScript
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.
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.
C++
Time Complexity: O(n), iterating over the string.
Space Complexity: O(n), for the dp array storage.
| 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. |
LeetCode was HARD until I Learned these 15 Patterns • Ashish Pratap Singh • 1,002,307 views views
Watch 9 more video solutions →Practice Find the Original Typed String II with our built-in code editor and test cases.
Practice on FleetCode