Watch 10 video solutions for Find the Original Typed String I, a easy level problem involving String. This walkthrough by codestorywithMIK has 7,972 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
Although Alice tried to focus on her typing, she is aware that she may still have done this at most once.
You are given a string word, which represents the final output displayed on Alice's screen.
Return the total number of possible original strings that Alice might have intended to type.
Example 1:
Input: word = "abbcccc"
Output: 5
Explanation:
The possible strings are: "abbcccc", "abbccc", "abbcc", "abbc", and "abcccc".
Example 2:
Input: word = "abcd"
Output: 1
Explanation:
The only possible string is "abcd".
Example 3:
Input: word = "aaaa"
Output: 4
Constraints:
1 <= word.length <= 100word consists only of lowercase English letters.Problem Overview: You are given a typed string where a character may appear multiple times consecutively due to a key being held down. The task is to determine how many possible original strings could produce this typed result.
Approach 1: Single Removal Examination (O(n^2) time, O(n) space)
A direct way to reason about the problem is to try removing one character from every index and check if the resulting string could reasonably be the original typed input. After removing a character, compare the compressed character runs of the candidate string with the typed string to see if the extra character could come from a long press. This brute-force validation approach simulates every possible removal and verifies consistency. It works well for understanding the mechanics of the problem but becomes inefficient because each removal requires rebuilding and scanning the string.
Approach 2: Character Compression Method (O(n) time, O(1) space)
The key observation is that only consecutive duplicate characters create ambiguity. If a run contains k identical characters, any one of the extra k-1 characters could have been produced by the long press. Each duplicate position therefore represents one additional possible original string where that character is removed. Iterate through the string and count positions where word[i] == word[i-1]. Each such occurrence contributes one more valid candidate. The final answer is duplicates + 1, where the extra 1 represents the case where the typed string already matches the original with no extra press.
This solution effectively performs a lightweight run-length scan, a common pattern in string processing problems. The algorithm uses a single pass through the input and constant memory, making it optimal for large inputs.
Recommended for interviews: The Character Compression Method is what interviewers typically expect. The brute-force removal approach shows you understand the problem mechanics, but the optimized scan demonstrates the ability to identify duplicate runs and reduce the problem to a linear array-style traversal with constant memory. Many string interview questions rely on recognizing these run-length patterns.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Single Removal Examination | O(n^2) | O(n) | Useful for understanding the mechanics of removing characters and validating candidate originals |
| Character Compression Method | O(n) | O(1) | Best choice for production or interviews; single scan counting duplicate runs |