Find the Original Typed String I
EasyPrompt
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.
Approaches
2 approaches with complexity analysis and trade-offs.
This approach breaks the problem into two distinct steps. First, it processes the input string to identify and store all groups of consecutive identical characters. For example, "abbcccc" would be represented as groups of ('a', 1), ('b', 2), and ('c', 4). In the second step, it calculates the number of possible original strings based on these stored groups.
Algorithm
- Create a list to store groups of characters. A group can be represented by a pair or a small array, e.g.,
(character, count). - Iterate through the input
wordfrom the beginning. - For each character, check if it's the same as the character of the last group added to the list.
- If it is, increment the count of the last group.
- If it's not, or if the list is empty, add a new group
(currentChar, 1)to the list. - After iterating through the entire word, initialize
totalPossibilitiesto 1. This accounts for the case where no long press occurred. - Iterate through the created list of groups.
- For each group
(char, count), ifcountis greater than 1, addcount - 1tototalPossibilities. - Return
totalPossibilities.
Walkthrough
The core idea is that a long press could have occurred on any character that appears consecutively more than once. The total number of possibilities is the sum of two scenarios:
- No long press: The original string is the same as the input
word. This accounts for one possibility. - Exactly one long press: A long press could have happened on any group of characters with a length greater than 1. For a group of length
k, there arek-1shorter original versions. For example, if we see "cccc" (length 4), the original could have been "ccc", "cc", or "c" (3 possibilities). We sum these possibilities for all eligible groups.
import java.util.ArrayList;import java.util.List; class Solution { // Using a simple class for groups for clarity static class Group { char character; int count; Group(char character, int count) { this.character = character; this.count = count; } } public int findOriginalTypedString(String word) { if (word == null || word.isEmpty()) { return 0; } List<Group> groups = new ArrayList<>(); for (char c : word.toCharArray()) { if (groups.isEmpty() || groups.get(groups.size() - 1).character != c) { groups.add(new Group(c, 1)); } else { groups.get(groups.size() - 1).count++; } } int totalPossibilities = 1; // Case with no long press for (Group group : groups) { if (group.count > 1) { totalPossibilities += (group.count - 1); } } return totalPossibilities; }}Complexity
Time
O(N), where N is the length of `word`. The first loop to create groups iterates through the string once. The second loop iterates through the groups, and the number of groups (K) is at most N. So, the total time is O(N + K) which simplifies to O(N).
Space
O(K), where K is the number of consecutive character groups. In the worst-case scenario (e.g., "abcdef"), K is equal to N (the length of the string), leading to O(N) space complexity.
Trade-offs
Pros
The logic is very clear and easy to follow as it's separated into two distinct phases: grouping and counting.
The separation of concerns can make the code easier to debug and maintain.
Cons
Requires extra space to store the character groups, which can be proportional to the length of the string in the worst case.
This is the most efficient approach, solving the problem in a single pass over the input string. It calculates the total number of possible original strings by identifying groups of consecutive characters and updating the total count on the fly, without needing any extra data structures to store the groups.
Algorithm
- Initialize
totalPossibilitiesto 1. This represents the case where the inputwordis the original string (no long presses). - Initialize a pointer
ito 0 to iterate through the string. - Use a
whileloop that continues as long asiis less than the string lengthn. - Inside the loop, use a second pointer
jstarting fromi + 1to find the end of the current consecutive character group. - The inner
whileloop incrementsjas long asj < nandword.charAt(j)is the same asword.charAt(i). - Once the inner loop finishes, the group of identical characters starts at
iand ends atj-1. The length of this group iscount = j - i. - If
countis greater than 1, it means this group could be the result of a long press. Addcount - 1tototalPossibilities. - Update the outer loop pointer
itojto move to the beginning of the next group. - After the outer loop completes, return
totalPossibilities.
Walkthrough
This approach combines the grouping and counting steps into a single, efficient pass. It maintains a running total of possibilities, initialized to 1 to account for the scenario with no typing errors.
As we iterate through the string, we identify the length of each consecutive character group. If a group's length, say k, is greater than 1, it implies this group could have been formed by a long press on a shorter sequence of the same character. The number of ways this could happen is k-1, which we add to our running total. By using a two-pointer technique, we can find the end of each group and continue the scan from the next new character, ensuring each character is processed only once.
class Solution { public int findOriginalTypedString(String word) { if (word == null || word.length() == 0) { return 0; } int n = word.length(); int totalPossibilities = 1; // Case with no long press int i = 0; while (i < n) { int j = i + 1; while (j < n && word.charAt(j) == word.charAt(i)) { j++; } // The group of identical characters is from index i to j-1 int count = j - i; if (count > 1) { // This group could have been formed from a shorter sequence // of length 1, 2, ..., count-1. This gives count-1 possibilities. totalPossibilities += (count - 1); } // Move to the start of the next group i = j; } return totalPossibilities; }}Complexity
Time
O(N), where N is the length of `word`. Although there is a nested `while` loop, the outer pointer `i` is always updated to the position of the inner pointer `j`. This ensures that each character in the string is visited exactly once across all iterations.
Space
O(1). We only use a few variables to keep track of indices and the total count, regardless of the input size.
Trade-offs
Pros
Extremely efficient in terms of space, using only a constant amount of extra memory.
Optimal time complexity as it processes the string in a single pass.
Cons
The nested loop structure, while efficient, might be slightly less intuitive at first glance compared to a two-step approach.
Solutions
Solution
class Solution: def possibleStringCount(self, word: str) -> int: return 1 + \ sum(x == y for x, y in pairwise(word))class Solution {public int possibleStringCount(String word) { int f = 1; for (int i = 1; i < word.length(); ++i) { if (word.charAt(i) == word.charAt(i - 1)) { ++f; } } return f; }}class Solution {public: int possibleStringCount(string word) { int f = 1; for (int i = 1; i < word.size(); ++i) { f += word[i] == word[i - 1]; } return f; }};Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.