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.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.
C
C++
Java
C#
JavaScript
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.
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.
C
C++
Java
C#
JavaScript
Time Complexity: O(n), iterating through the character string once.
Space Complexity: O(1), as only counters and iterators are used.
| 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. |
How to Start Leetcode (as a beginner) • Ashish Pratap Singh • 1,177,678 views views
Watch 9 more video solutions →Practice Find the Original Typed String I with our built-in code editor and test cases.
Practice on FleetCode