Find the Original Typed String I — Problem & Solution
Find the Original Typed String I solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem.
Find the Original Typed String I is an easy coding problem on strings, asked in Amazon, Google and Accenture interviews.
- Difficulty: Easy
- Topics: Strings
- Asked at: Amazon, Google, Accenture
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
A typist may have held one key down too long, repeating a single character extra times — but this happened at most once in the whole word.
Given the string word that appeared on screen, return the number of strings that could have been intended.
Example 1
Input: word = "abbcccc"
Output: 5
Explanation: The word itself, plus `abcccc`, `abbccc`, `abbcc` and `abbc`.
Example 2
Input: word = "abcd"
Output: 1
Explanation: Nothing repeats, so nothing was held down.
Example 3
Input: word = "aaaa"
Output: 4
Explanation: The original could have been 1, 2, 3 or 4 `a`s.
Constraints
1 <= word.length <= 100word consists of lowercase English letters.
Hints for Find the Original Typed String I
Hint 1
If the long press happened in a run of length
L, the original had that run at any length from 1 toL.Hint 2
That is
L - 1shortened possibilities per run, plus the one where nothing was held down.Hint 3
Summing
L - 1over every run is the same as counting adjacent equal pairs.
How to solve Find the Original Typed String I
Exactly one run may have been stretched. A run of length L yields L - 1 shorter originals, and one more possibility covers "no long press at all". Summing L - 1 across the runs is precisely the number of adjacent equal character pairs.
Approach
- Start the count at 1 — the word as typed.
- Add one for each index where the character equals its predecessor.
Why it works
The "at most once" clause is what makes the runs independent rather than multiplicative: you pick one run and one shortened length, so the possibilities add rather than multiply. Counting adjacent equal pairs is the same sum written without ever identifying the run boundaries.
Complexity
- Time —
O(n) - Space —
O(1)
Pitfalls
- Adding 1 for the untouched word is easy to forget, and it is always a possibility.
- The runs add, not multiply — only one key was held.
- A run of length 1 contributes nothing.
Reference solution
Python
def possibleStringCount(word: str) -> int:
return 1 + sum(1 for i in range(1, len(word)) if word[i] == word[i - 1])Java
public static int possibleStringCount(String word) {
int total = 1;
for (int i = 1; i < word.length(); i++) {
if (word.charAt(i) == word.charAt(i - 1)) total++;
}
return total;
}C++
int possibleStringCount(string word) {
int total = 1;
for (size_t i = 1; i < word.size(); i++) {
if (word[i] == word[i - 1]) total++;
}
return total;
}JavaScript
var possibleStringCount = function(word) {
var total = 1;
for (var i = 1; i < word.length; i++) {
if (word.charAt(i) === word.charAt(i - 1)) total++;
}
return total;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 515 strings problems · the whole catalogue
Learn the technique: Strings