[LeetCode] 3330. Find the Original Typed String I

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 <= 100
word consists only of lowercase English letters.

找到初始输入字符串 I。

Alice 正在她的电脑上输入一个字符串。但是她打字技术比较笨拙,她 可能 在一个按键上按太久,导致一个字符被输入 多次 。

尽管 Alice 尽可能集中注意力,她仍然可能会犯错 至多 一次。

给你一个字符串 word ,它表示 最终 显示在 Alice 显示屏上的结果。

请你返回 Alice 一开始可能想要输入字符串的总方案数。

思路

这道题不涉及算法,注意观察字符串的规律。如果相邻的字符相同,那么第二个字母就有可能是一次重复的输入。所以我们可以遍历 input 字符串,如果当前字母跟前一个字母不一样,则说明没有犯错;如果跟前一个字母一样,那么第二个字母就有可能是因为犯错而输入的,则计数加一。

复杂度

时间O(n)
空间O(1)

代码

Java实现

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public int possibleStringCount(String word) {
int count = 1;
int n = word.length();
for (int i = 1; i < n; i++) {
if (word.charAt(i) == word.charAt(i - 1)) {
count++;
}
}
return count;
}
}

[LeetCode] 3330. Find the Original Typed String I
https://shurui91.github.io/posts/528034947.html
Author
Aaron Liu
Posted on
June 30, 2025
Licensed under