Find the Original Typed String II - Video Solutions

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.