Find the Original Typed String I solution and explanation
TCS
Google
9 more videos on this problem
Find the Original Typed String I | Straight Forward | Leetcode 3330 | codestorywithMIKcodestorywithMIK · 10:28 · 8K views
3330. Find the Original Typed String I | Leetcode Daily - PythonLeetcode Daily · 5:27 · 832 views
Find the Original Typed String I | LeetCode 3330 | String | Easy | Beginner FriendlyCode Harmony · 10:35 · 174 views
3330. Find the Original Typed String I - LeetCode [Easy] POTD - 1 June 2025Intuit & Code · 12:46 · 129 views
Find the Original Typed String I | LeetCode 3330 - Pythonimpoldev · 6:31 · 122 views
LeetCode 3330 Find the Original Typed String IEducation, the study of everything · 6:35 · 68 views
Leetcode: 3330. Find the Original Typed String IDilan Rocco · 9:50 · 60 views
LeetCode 3330 | Find the Original Typed String I – Java Solution with Submission LinkTech AutoWired · 4:20 · 53 views
Leetcode 3330 Find the Original Typed String ISimrat Hanspal · 7:46 · 49 views
LeetCode 3330: Find the Original Typed String I | Java Solution |Code Scribbler · 7:41 · 24 views
The problem
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.
def count_possible_strings(word):
n = len(word)
count = 0
i = 0
while i < n:
char_count = 1
while i + 1 < n and word[i] == word[i + 1]:
i += 1
char_count += 1
count += char_count
i += 1
return count
# Example Usage
result = count_possible_strings("abbcccc")
print(result) # Output: 5class Main {
public static int countPossibleStrings(String word) {
int n = word.length();
int count = 0;
int i = 0;
while (i < n) {
int charCount = 1;
while (i + 1 < n && word.charAt(i) == word.charAt(i + 1)) {
i++;
charCount++;
}
count += charCount;
i++;
}
return count;
}
public static void main(String[] args) {
System.out.println(countPossibleStrings("abbcccc")); // Output: 5
}
}#include <iostream>
#include <string>
using namespace std;
int countPossibleStrings(const string& word) {
int n = word.length();
int count = 0;
int i = 0;
while (i < n) {
int charCount = 1;
while (i + 1 < n && word[i] == word[i + 1]) {
i++;
charCount++;
}
count += charCount;
i++;
}
return count;
}
int main() {
cout << countPossibleStrings("abbcccc") << endl;
return 0;
}function countPossibleStrings(word) {
const n = word.length;
let count = 0;
let i = 0;
while (i < n) {
let charCount = 1;
while (i + 1 < n && word[i] === word[i + 1]) {
i++;
charCount++;
}
count += charCount;
i++;
}
return count;
}
console.log(countPossibleStrings("abbcccc")); // Output: 5#include <stdio.h>
#include <string.h>
int countPossibleStrings(const char *word) {
int n = strlen(word);
int count = 0;
int i = 0;
while (i < n) {
int charCount = 1;
while (i + 1 < n && word[i] == word[i + 1]) {
i++;
charCount++;
}
count += charCount;
i++;
}
return count;
}
int main() {
printf("%d\n", countPossibleStrings("abbcccc"));
return 0;
}using System;
class Program {
static int CountPossibleStrings(string word) {
int n = word.Length;
int count = 0;
int i = 0;
while (i < n) {
int charCount = 1;
while (i + 1 < n && word[i] == word[i + 1]) {
i++;
charCount++;
}
count += charCount;
i++;
}
return count;
}
static void Main(string[] args) {
Console.WriteLine(CountPossibleStrings("abbcccc"));
}
}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.
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.
def count_possible_strings(word):
n = len(word)
total = 1
i = 0
while i < n:
char_count = 1
while i + 1 < n and word[i] == word[i + 1]:
i += 1
char_count += 1
total += char_count - 1
i += 1
return total
# Example Usage
result = count_possible_strings("aaaa")
print(result) # Output: 4class Main {
public static int countPossibleStrings(String word) {
int n = word.length();
int total = 1;
int i = 0;
while (i < n) {
int charCount = 1;
while (i + 1 < n && word.charAt(i) == word.charAt(i + 1)) {
i++;
charCount++;
}
total += charCount - 1;
i++;
}
return total;
}
public static void main(String[] args) {
System.out.println(countPossibleStrings("aaaa")); // Output: 4
}
}#include <iostream>
#include <string>
using namespace std;
int countPossibleStrings(const string& word) {
int n = word.length();
int total = 1;
int i = 0;
while (i < n) {
int charCount = 1;
while (i + 1 < n && word[i] == word[i + 1]) {
i++;
charCount++;
}
total += charCount - 1;
i++;
}
return total;
}
int main() {
cout << countPossibleStrings("aaaa") << endl;
return 0;
}function countPossibleStrings(word) {
const n = word.length;
let total = 1;
let i = 0;
while (i < n) {
let charCount = 1;
while (i + 1 < n && word[i] === word[i + 1]) {
i++;
charCount++;
}
total += charCount - 1;
i++;
}
return total;
}
console.log(countPossibleStrings("aaaa")); // Output: 4#include <stdio.h>
#include <string.h>
int countPossibleStrings(const char *word) {
int n = strlen(word);
int total = 1;
int i = 0;
while (i < n) {
int charCount = 1;
while (i + 1 < n && word[i] == word[i + 1]) {
i++;
charCount++;
}
total += charCount - 1;
i++;
}
return total;
}
int main() {
printf("%d\n", countPossibleStrings("aaaa"));
return 0;
}using System;
class Program {
static int CountPossibleStrings(string word) {
int n = word.Length;
int total = 1;
int i = 0;
while (i < n) {
int charCount = 1;
while (i + 1 < n && word[i] == word[i + 1]) {
i++;
charCount++;
}
total += charCount - 1;
i++;
}
return total;
}
static void Main(string[] args) {
Console.WriteLine(CountPossibleStrings("aaaa"));
}
}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.
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).
function possibleStringCount(word: string): number {
let f = 1;
for (let i = 1; i < word.length; ++i) {
f += word[i] === word[i - 1] ? 1 : 0;
}
return f;
}func possibleStringCount(word string) int {
f := 1
for i := 1; i < len(word); i++ {
if word[i] == word[i-1] {
f++
}
}
return f
}impl Solution {
pub fn possible_string_count(word: String) -> i32 {
1 + word.as_bytes().windows(2).filter(|w| w[0] == w[1]).count() as i32
}
}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 | – |
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 |
Frequently asked questions
Is Find the Original Typed String I easy or hard?
Find the Original Typed String I is classified as an Easy problem with an acceptance rate above 70%. It mainly tests the ability to recognize consecutive character patterns and apply a simple linear scan.
Find the Original Typed String I Python/Java solution
The implementation is straightforward in Python, Java, C++, and other languages. Loop through the string, compare each character with the previous one, and increment a counter when they match. Return duplicates + 1 as the number of possible original strings.
How to solve Find the Original Typed String I in O(n)?
Iterate through the string and check whether the current character equals the previous one. Each time this happens, increment a duplicate counter. The final answer is duplicates + 1, representing all possible original strings formed by removing one of the repeated characters or keeping the string unchanged.
What is the best approach for Find the Original Typed String I?
The Character Compression Method is the optimal solution. Scan the string once and count how many times consecutive characters are equal. Each duplicate position represents one extra possible original string, leading to an O(n) time and O(1) space solution.
Is Find the Original Typed String I asked at Google/Amazon/Meta?
Problems involving string compression, duplicate runs, and long‑press typing patterns frequently appear in interviews at companies like Google, Amazon, and Meta. While the exact problem may vary, the underlying technique of scanning consecutive characters is common.
What data structure is used in Find the Original Typed String I?
The solution primarily uses basic string traversal. No additional data structures are required beyond a few counters, which keeps the space complexity constant.
What is the time complexity of Find the Original Typed String I?
The optimal solution runs in O(n) time because it performs a single pass through the string. Space complexity is O(1) since only a counter variable is needed to track duplicate characters.