#3333

Hard

auto_awesomeState transition dynamic programming

LeetCode Problem Workspace

Find the Original Typed String II

Calculate how many potential original strings Alice might have intended to type, considering her clumsy typing behavior.

string dynamic programming prefix sum

Problem Statement

Alice is typing a string on her computer, but she often presses keys too long, resulting in multiple occurrences of the same character in the final output. You are given a string, word, which represents the final string displayed on Alice's screen, and an integer k that defines the minimum length of the original intended string.

Your task is to determine how many possible original strings Alice could have been attempting to type, where the original string’s length is at least k. The solution should be efficient enough to handle the constraints of the problem where word can have a length up to 500,000.

Examples

Example 1

Input: word = "aabbccdd", k = 7

Output: 5

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

Example 2

Input: word = "aabbccdd", k = 8

Output: 1

The only possible string is "aabbccdd" .

Example 3

Input: word = "aaabbb", k = 3

Output: 8

Example details omitted.

Constraints

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

Solution Approach

State Transition Dynamic Programming

Use dynamic programming to break down the problem. Instead of solving for all strings with length at least k, solve for strings with lengths at most k-1 and adjust the state transition logic to count potential valid subsequences efficiently.

Prefix Sum Optimization

Utilize prefix sums to speed up the calculation of potential subsequences by caching intermediate results, which reduces the number of redundant calculations and optimizes the solution for large inputs.

Iterative DP Array Update

Iterate through the string and update a dynamic programming array that tracks the possible ways to form strings of each length. This array will use previous results to compute the number of valid strings at each step.

Complexity Analysis

Metric	Value
Time	O(n + k^2)
Space	O(k)

The time complexity is O(n + k^2) because we loop through the string once (O(n)) and process dynamic programming transitions for each length from 1 to k (O(k^2)). The space complexity is O(k) due to the use of a DP array to store intermediate results for lengths up to k.

What Interviewers Usually Probe

Looking for understanding of dynamic programming with state transitions.
Tests problem-solving skills in reducing complexity by optimizing state transitions.
Evaluates how well the candidate handles constraints and optimizes large inputs.

Common Pitfalls or Variants

Common pitfalls

Failing to handle large input sizes efficiently, resulting in time complexity issues.
Not utilizing prefix sums to optimize dynamic programming transitions.
Misunderstanding the transition state and incorrectly counting valid subsequences.

Follow-up variants

Implementing a solution with different constraints, like a different maximum length for word.
Reducing the value of k and testing the edge cases for smaller inputs.
Applying the same approach to variations of this problem, like different typing mistakes or different characters.

FAQ

What is the primary pattern used in the "Find the Original Typed String II" problem?

The primary pattern is state transition dynamic programming, which helps efficiently compute valid subsequences.

How does prefix sum optimization benefit the solution?

Prefix sum optimization helps by caching intermediate results, reducing redundant calculations and improving performance for large inputs.

What is the time complexity of the solution?

The time complexity is O(n + k^2), where n is the length of the string word and k is the maximum string length to consider.

Can this problem be solved with a greedy approach?

No, a greedy approach would not efficiently handle the constraints of the problem. Dynamic programming is required to explore all valid subsequences.

What are the key challenges in solving "Find the Original Typed String II"?

Key challenges include efficiently managing large inputs, understanding the state transition dynamic programming, and correctly counting valid subsequences.

terminal

Solution

Solution 1: Dynamic Programming + Prefix Sum

For the constraint that the length is at least $k$, we can split it into two subproblems:

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

class Solution:
    def possibleStringCount(self, word: str, k: int) -> int:
        mod = 10**9 + 7
        nums = []
        ans = 1
        cur = 0
        for i, c in enumerate(word):
            cur += 1
            if i == len(word) - 1 or c != word[i + 1]:
                if cur > 1:
                    if k > 0:
                        nums.append(cur - 1)
                    ans = ans * cur % mod
                cur = 0
                k -= 1
        if k < 1:
            return ans
        m = len(nums)
        f = [[0] * k for _ in range(m + 1)]
        f[0][0] = 1
        for i, x in enumerate(nums, 1):
            s = list(accumulate(f[i - 1], initial=0))
            for j in range(k):
                f[i][j] = (s[j + 1] - s[j - min(x, j)] + mod) % mod
        return (ans - sum(f[m][j] for j in range(k))) % mod

Continue Practicing

#3335 total characters in string after transformations i #3337 total characters in string after transformations ii #3343 count number of balanced permutations