LeetCode 题解工作台
删除字符使字符串变好
一个字符串如果没有 三个连续 相同字符，那么它就是一个 好字符串 。 给你一个字符串 s ，请你从 s 删除 最少 的字符，使它变成一个 好字符串 。 请你返回删除后的字符串。题目数据保证答案总是 唯一的 。 示例 1： 输入： s = "le e etcode" 输出： "leetcode" 解释…
1
题型
7
代码语言
3
相关题
当前训练重点
简单 · String-driven solution strategy
答案摘要
我们可以遍历字符串 ，并使用一个数组 记录当前的答案。对于每一个字符 ，如果 $i \lt 2$ 或者 与 $s[i - 1]$ 不等，或者 与 $s[i - 2]$ 不等，我们就将 添加到 中。 最后，我们将 中的字符连接起来，就得到了答案。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 String-driven solution strategy 题型思路
题目描述
一个字符串如果没有 三个连续 相同字符，那么它就是一个 好字符串 。
给你一个字符串 s ，请你从 s 删除 最少 的字符，使它变成一个 好字符串 。
请你返回删除后的字符串。题目数据保证答案总是 唯一的 。
示例 1：
输入：s = "leeetcode" 输出："leetcode" 解释： 从第一组 'e' 里面删除一个 'e' ，得到 "leetcode" 。 没有连续三个相同字符，所以返回 "leetcode" 。
示例 2：
输入：s = "aaabaaaa" 输出："aabaa" 解释： 从第一组 'a' 里面删除一个 'a' ，得到 "aabaaaa" 。 从第二组 'a' 里面删除两个 'a' ，得到 "aabaa" 。 没有连续三个相同字符，所以返回 "aabaa" 。
示例 3：
输入：s = "aab" 输出："aab" 解释：没有连续三个相同字符，所以返回 "aab" 。
提示：
1 <= s.length <= 105s只包含小写英文字母。
解题思路
方法一：模拟
我们可以遍历字符串 ，并使用一个数组 记录当前的答案。对于每一个字符 ，如果 或者 与 不等，或者 与 不等，我们就将 添加到 中。
最后，我们将 中的字符连接起来，就得到了答案。
时间复杂度 ，其中 为字符串 的长度。忽略答案的空间消耗，空间复杂度 。
class Solution:
def makeFancyString(self, s: str) -> str:
ans = []
for i, c in enumerate(s):
if i < 2 or c != s[i - 1] or c != s[i - 2]:
ans.append(c)
return "".join(ans)
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | O(n) |
| 空间 | O(1) |
面试官常问的追问
外企场景- question_mark
Candidate demonstrates a clear understanding of how to traverse the string efficiently.
- question_mark
Candidate handles edge cases correctly, ensuring no deletions when unnecessary.
- question_mark
Candidate focuses on the O(n) time complexity and avoids unnecessary space usage.
常见陷阱
外企场景- error
Forgetting to handle edge cases like strings with no triplets.
- error
Not considering the in-place deletion, leading to unnecessary space usage.
- error
Improperly handling the first and last characters, which may not be part of a triplet.
进阶变体
外企场景- arrow_right_alt
Extend the problem to handle uppercase letters as well.
- arrow_right_alt
Alter the problem to allow a configurable number of consecutive characters.
- arrow_right_alt
Change the problem to return the number of deletions instead of the final string.