LeetCode 题解工作台
构造有效字符串的最少插入数
给你一个字符串 word ，你可以向其中任何位置插入 "a"、"b" 或 "c" 任意次，返回使 word 有效 需要插入的最少字母数。 如果字符串可以由 "abc" 串联多次得到，则认为该字符串 有效 。 示例 1： 输入： word = "b" 输出： 2 解释： 在 "b" 之前插入 "a" …
4
题型
5
代码语言
3
相关题
当前训练重点
中等 · 状态·转移·动态规划
答案摘要
我们定义字符串 为 `"abc"`，用指针 和 分别指向 和 。 如果 $word[j] \neq s[i]$，则需要插入 ，我们将答案加 ；否则，说明 可以与 匹配，我们将 右移一位。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 状态·转移·动态规划 题型思路
题目描述
给你一个字符串 word ，你可以向其中任何位置插入 "a"、"b" 或 "c" 任意次，返回使 word 有效 需要插入的最少字母数。
如果字符串可以由 "abc" 串联多次得到，则认为该字符串 有效 。
示例 1：
输入：word = "b" 输出：2 解释：在 "b" 之前插入 "a" ，在 "b" 之后插入 "c" 可以得到有效字符串 "abc" 。
示例 2：
输入：word = "aaa" 输出：6 解释：在每个 "a" 之后依次插入 "b" 和 "c" 可以得到有效字符串 "abcabcabc" 。
示例 3：
输入：word = "abc" 输出：0 解释：word 已经是有效字符串，不需要进行修改。
提示：
1 <= word.length <= 50word仅由字母 "a"、"b" 和 "c" 组成。
解题思路
方法一：贪心 + 双指针
我们定义字符串 为 "abc"，用指针 和 分别指向 和 。
如果 ，则需要插入 ，我们将答案加 ；否则，说明 可以与 匹配，我们将 右移一位。
然后，我们将 右移一位，即 。继续上述操作，直到 到达字符串 的末尾。
最后，我们判断 的最后一个字符是否为 'b' 或者 'a'，如果是，则需要插入 'c' 或者 'bc'，我们将答案加 或者 后返回即可。
时间复杂度 ，其中 为字符串 的长度。空间复杂度 。
class Solution:
def addMinimum(self, word: str) -> int:
s = 'abc'
ans, n = 0, len(word)
i = j = 0
while j < n:
if word[j] != s[i]:
ans += 1
else:
j += 1
i = (i + 1) % 3
if word[-1] != 'c':
ans += 1 if word[-1] == 'b' else 2
return ans
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity is O(n) for scanning the string with a pointer, or O(n) using DP for state transitions over word length n. Space complexity is O(1) for greedy approach or O(n) for DP array storing minimal insertions. |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Check if candidates can maintain the cyclic 'abc' state efficiently.
- question_mark
Observe whether they identify insertion points greedily or use dynamic programming.
- question_mark
Look for handling of consecutive missing characters without over-inserting.
常见陷阱
外企场景- error
Failing to cycle through 'abc' correctly when characters repeat.
- error
Overcounting insertions by not considering the expected sequence state.
- error
Using brute-force insertion checking instead of a DP or pointer-based approach.
进阶变体
外企场景- arrow_right_alt
Allow additional letters beyond 'a', 'b', 'c' and compute minimal deletions to restore validity.
- arrow_right_alt
Find the minimal number of deletions instead of insertions to achieve valid repeated 'abc' segments.
- arrow_right_alt
Compute minimal insertions when word must form 'xyz' repeated patterns instead of 'abc'.