Practice Find the Original Typed String I
Read the task, work through the examples, and check your approach against the constraints. Use the original LeetCode task for coding and submissions.
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.
Source: Find the Original Typed String I on LeetCode. Use the original task for its coding environment and submissions.
Examples
# Example 1
word = "abbcccc"
5
The five possible originals are "abbcccc", "abcccc", "abbccc", "abbcc" and "abbc". The unchanged string covers no typing error. Alternatively, shorten the run "bb" in one way or the run "cccc" in three ways, giving 1 + 1 + 3 = 5. Do not also include strings such as "abcc": shortening both runs would require two separate long key presses, but at most one is allowed. Count shortened run lengths, not which identical character within a run was held down.
# Example 2
word = "abcd"
1
All four adjacent characters are different. A long key press would have produced repeated adjacent copies of the same character, and no such run appears. The only possible original is therefore "abcd", giving 1. The unchanged string must be counted because the error happened at most once, so it is permitted to have happened zero times.
# Example 3
word = "aaaa"
4
The original can be "a", "aa", "aaa" or "aaaa", so the answer is 4. A single long key press can create several extra copies, which allows each shorter length from 1 through 3; the length-4 string represents no error. All characters belong to one run, so shortening different positions to the same length does not create a different original. The empty string is impossible because the long press repeats an intended character rather than inventing one.
Constraints
How to solve Find the Original Typed String I
Original notes for interview preparation, written for this problem. Reviewed .
Key insight
A single long key press can only lengthen one run of identical letters, and shortening a run of length L to any length from 1 to L - 1 gives L - 1 distinct originals. So the answer is 1 for the unchanged word plus the total of (run length - 1) over all runs, which equals 1 plus the number of positions whose character equals the previous one.
Why brute force is not enough
Generating every candidate original by deleting a block of characters inside one run, storing them in a set to remove duplicates, and counting costs about O(n^3) in time and memory for strings up to 100 characters; it passes but double counts easily unless deduplicated.
Approach
- Start the count at 1 to represent the possibility that no key was held too long and the word is exactly what was intended.
- Scan the word from the second character onward, comparing each character with the one before it.
- Each time a character equals its predecessor, add one. The invariant is that the running total equals 1 plus the sum over runs seen so far of run length minus one, since a run of length L contributes exactly L - 1 such equal-neighbor positions.
- Return the total after the scan. Each shortened run length corresponds to one distinct original string, and shortening two different runs would require two errors, which is forbidden.
Walkthrough of Example 1
word = "abbcccc" → 5
- word is "abbcccc". Start the count at 1 for the unchanged string.
- Index 1 (b) differs from a, no change. Index 2 (b) equals the previous b, count becomes 2.
- Index 3 (c) differs from b. Indices 4, 5, 6 are each c equal to the previous c, count becomes 3, 4, 5.
- The count 5 matches the expected output: the unchanged word, bb shortened to b, and cccc shortened to ccc, cc, or c.
Time and space
Time O(n) · Space O(1). n is the word length; a single pass with one counter handles everything.
Interview pitfalls
- Counting runs rather than extra characters, which gives 3 instead of 5 on the first example.
- Treating different positions within a run as different originals; holding any one of the identical keys produces the same string.
- Forgetting the unchanged word, since at most once includes zero times.
- Allowing two runs to be shortened at once, which models two separate errors.
- Returning 0 or the length for a one-character word; the only original is the word itself, so the answer is 1.
Follow-up questions interviewers ask
- If the error could happen at most twice, how do you count distinct originals without double counting the single-error cases?
- How does the count change if the original string must have length at least k?
- Could you count originals when a held key can also skip a letter, producing both repeats and omissions?
Further reading on the technique: Run-length encoding
Related LeetCode Problems
Practice more problems similar to Find the Original Typed String I.
Review your practice with PhantomCodeAI
After trying the problem yourself, use the app to discuss your approach, complexity, and edge cases.