LeetCode 题解工作台
找到初始输入字符串 I
Alice 正在她的电脑上输入一个字符串。但是她打字技术比较笨拙，她 可能 在一个按键上按太久，导致一个字符被输入 多次 。 尽管 Alice 尽可能集中注意力，她仍然可能会犯错 至多 一次。 给你一个字符串 word ，它表示 最终 显示在 Alice 显示屏上的结果。 请你返回 Alice 一开…
1
题型
6
代码语言
3
相关题
当前训练重点
简单 · String-driven solution strategy
答案摘要
根据题目描述，如果所有相邻字符都不相同，那么只有 1 种可能的输入字符串；如果有 1 对相邻字符相同，例如 "abbc"，那么可能的输入字符串有 2 种："abc" 和 "abbc"。 依此类推，如果有 对相邻字符相同，那么可能的输入字符串有 $k + 1$ 种。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 String-driven solution strategy 题型思路
题目描述
Alice 正在她的电脑上输入一个字符串。但是她打字技术比较笨拙，她 可能 在一个按键上按太久，导致一个字符被输入 多次 。
尽管 Alice 尽可能集中注意力，她仍然可能会犯错 至多 一次。
给你一个字符串 word ，它表示 最终 显示在 Alice 显示屏上的结果。
请你返回 Alice 一开始可能想要输入字符串的总方案数。
示例 1：
输入：word = "abbcccc"
输出：5
解释：
可能的字符串包括："abbcccc" ，"abbccc" ，"abbcc" ，"abbc" 和 "abcccc" 。
示例 2：
输入：word = "abcd"
输出：1
解释：
唯一可能的字符串是 "abcd" 。
示例 3：
输入：word = "aaaa"
输出：4
提示：
1 <= word.length <= 100word只包含小写英文字母。
解题思路
方法一：直接遍历
根据题目描述，如果所有相邻字符都不相同，那么只有 1 种可能的输入字符串；如果有 1 对相邻字符相同，例如 "abbc"，那么可能的输入字符串有 2 种："abc" 和 "abbc"。
依此类推，如果有 对相邻字符相同，那么可能的输入字符串有 种。
因此，我们只需要遍历字符串，统计相邻字符相同的对数再加 1 即可。
时间复杂度 ，其中 为字符串的长度。空间复杂度 。
class Solution:
def possibleStringCount(self, word: str) -> int:
return 1 + sum(x == y for x, y in pairwise(word))
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | O(n) |
| 空间 | O(1) |
面试官常问的追问
外企场景- question_mark
Notice patterns of consecutive repeated letters to test the candidate's string analysis skills.
- question_mark
Ask why simply counting characters may overestimate the original length if repeated presses occur.
- question_mark
Look for recognition that at most one accidental repetition per group affects the valid original count.
常见陷阱
外企场景- error
Assuming all repeated characters are intentional, which overcounts the original string length.
- error
Failing to handle single-character groups correctly, leading to off-by-one errors.
- error
Using extra data structures unnecessarily, increasing space complexity beyond O(1).
进阶变体
外企场景- arrow_right_alt
Allow multiple accidental repeats per character group instead of at most one.
- arrow_right_alt
Determine the minimum possible length of the original string instead of the maximum.
- arrow_right_alt
Extend the problem to uppercase letters or digits to test general string handling.