Easy

题目描述

一个好字符串是指没有三个连续字符相等的字符串。

给你一个字符串 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 <= 10^5
  • s 仅由小写英文字母组成

提示：

  • 如果三个或更多连续字符相等，删除字符的最优方法是什么？
  • 如果三个或更多连续字符相等，保留其中两个，删除其余的。

解题思路

解题思路

这道题要求删除最少字符使得字符串中没有三个连续相等的字符。关键观察是：当遇到三个或更多连续相等字符时，我们只需要保留前两个，删除后面的即可。

方法一：贪心算法（推荐）

我们可以遍历字符串，维护一个结果字符串。对于每个字符，检查它与结果字符串末尾的两个字符是否相同。如果相同，说明会形成三个连续相等字符，我们就跳过这个字符；否则将其添加到结果中。

具体步骤：

  1. 遍历输入字符串的每个字符
  2. 检查当前字符是否会与结果字符串末尾形成三个连续相等字符
  3. 如果不会，则添加到结果中；如果会，则跳过

方法二：计数法

另一种思路是记录连续相同字符的个数，当个数超过2时停止添加。但这种方法实现相对复杂一些。

贪心算法时间复杂度为O(n)，空间复杂度为O(1)（不考虑输出空间），是最优解法。

代码实现

class Solution {
public:
    string makeFancyString(string s) {
        string result;
        
        for (char c : s) {
            int len = result.length();
            if (len >= 2 && result[len-1] == c && result[len-2] == c) {
                continue;
            }
            result += c;
        }
        
        return result;
    }
};

class Solution:
    def makeFancyString(self, s: str) -> str:
        result = []
        
        for c in s:
            if len(result) >= 2 and result[-1] == c and result[-2] == c:
                continue
            result.append(c)
        
        return ''.join(result)

public class Solution {
    public string MakeFancyString(string s) {
        StringBuilder result = new StringBuilder();
        
        foreach (char c in s) {
            int len = result.Length;
            if (len >= 2 && result[len-1] == c && result[len-2] == c) {
                continue;
            }
            result.Append(c);
        }
        
        return result.ToString();
    }
}

var makeFancyString = function(s) {
    let result = [];
    
    for (let c of s) {
        let len = result.length;
        if (len >= 2 && result[len-1]
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n)需要遍历字符串一次，每次操作都是常数时间
空间复杂度O(1)不考虑输出空间的话，只使用了常数额外空间

相关题目