原文链接: https://leetcode-cn.com/problems/delete-characters-to-make-fancy-string

英文原文

A fancy string is a string where no three consecutive characters are equal.

Given a string s, delete the minimum possible number of characters from s to make it fancy.

Return the final string after the deletion. It can be shown that the answer will always be unique.

 

Example 1:

Input: s = "leeetcode"
Output: "leetcode"
Explanation:
Remove an 'e' from the first group of 'e's to create "leetcode".
No three consecutive characters are equal, so return "leetcode".

Example 2:

Input: s = "aaabaaaa"
Output: "aabaa"
Explanation:
Remove an 'a' from the first group of 'a's to create "aabaaaa".
Remove two 'a's from the second group of 'a's to create "aabaa".
No three consecutive characters are equal, so return "aabaa".

Example 3:

Input: s = "aab"
Output: "aab"
Explanation: No three consecutive characters are equal, so return "aab".

 

Constraints:

• 1 <= s.length <= 105
• s consists only of lowercase English letters.

中文题目

一个字符串如果没有 三个连续 相同字符，那么它就是一个 好字符串 。

给你一个字符串 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 <= 105
• s 只包含小写英文字母。

通过代码

高赞题解

5193. 删除字符使字符串变好

​ 第一道题。

​ 要我们删掉字符串中一部分的字母，使这个字符串能没有一个片段连续三个字母相同。

在string上一个一个的删会超时，所以改成了用char记录新的字符串。

class Solution {
public:
    string makeFancyString(string s) {
        const int n = s.size();
        char ans[n + 1];  //用char存储新字符串
        ans[0] = s[0];  //记录第一个字符
        int j = 1;
        for(int i = 1; i < n; ++i, ++j){
            ans[j] = s[i];    //记录下这个字符
            if(ans[j] == ans[j - 1]){  //如果和先前字符相等
                while(i < n && s[i] == ans[j]) ++i;//一直遍历到与该字符不等的地方
                --i;  //后面还有++i，这里先减一下
            }
        }
        ans[j] = '\0';  //最后的中止符
        return ans;
    }
};

统计信息

通过次数	提交次数	AC比率
5173	8520	60.7%

提交历史

提交时间	提交结果	执行时间	内存消耗	语言