Find the Original Typed String I - 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.
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 <= 100wordconsists only of lowercase English letters.
Approach Overview
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 1: Character Compression Method
This method revolves around counting the consecutive occurrences of each character in the string. For each sequence of repeated characters, calculate how many shorter sequences (where some of the repetitions have been removed) can be formed. This provides the potential original forms the string may have taken.
For a sequence of length n of a repeating character, the potential original forms are all of those using 1 to n. As such, for each sequence of characters, the contribution to the potential total is n.
The above Python implementation iterates over the input string word, counts the consecutive characters, and calculates the total possible original forms. Each group of consecutive characters contributes to the count based on its length. This solution is efficient, leveraging simple arithmetic and iteration.
Complexity
Time Complexity: O(n) as each character in the string is visited once.
Space Complexity: O(1) as no additional space is required based on input size.
Approach 2: Single Removal Examination
This approach examines the possibility of removing exactly one character from any sequence of repeating characters. We iterate through the string, and whenever we encounter a block of repeating characters, we consider forming original strings by shortening the sequence by one character from any position.
This approach may involve keeping track of segments and choosing different positions to eliminate redundancy.
This Python implementation checks block size and calculates the potential original forms by considering removing a single occurrence from each sequence of the same characters. Smaller blocks inherently contribute one less than their size in potential 'removal' options.
Complexity
Time Complexity: O(n), iterating through the character string once.
Space Complexity: O(1), as only counters and iterators are used.
Approach 3: Direct Traversal
According to the problem description, if all adjacent characters are different, there is only 1 possible original input string. If there is 1 pair of adjacent identical characters, such as "abbc", then there are 2 possible original strings: "abc" and "abbc".
By analogy, if there are k pairs of adjacent identical characters, then there are k + 1 possible original input strings.
Therefore, we just need to traverse the string, count the number of pairs of adjacent identical characters, and add 1.
The time complexity is O(n), where n is the length of the string. The space complexity is O(1).
Complexity Comparison
| Approach | Complexity |
|---|---|
| Character Compression Method | Time Complexity: O(n) as each character in the string is visited once. |
| Single Removal Examination | Time Complexity: O(n), iterating through the character string once. |
| Direct Traversal | — |
Detailed Complexity Analysis
| 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 |
Video Solution
Find the Original Typed String I | Straight Forward | Leetcode 3330 | codestorywithMIK • codestorywithMIK • 8,091 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Find the Original Typed String I easy or hard?
Find the Original Typed String I Python/Java solution
How to solve Find the Original Typed String I in O(n)?
What is the best approach for Find the Original Typed String I?
Is Find the Original Typed String I asked at Google/Amazon/Meta?
What data structure is used in Find the Original Typed String I?
What is the time complexity of Find the Original Typed String I?
Ready to solve this problem?
Practice Find the Original Typed String I with our built-in code editor and test cases.
Practice on FleetCode