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

题目描述

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

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

解法

方法一：模拟

我们可以遍历字符串 \(s\)，并使用一个数组 \(\textit{ans}\) 记录当前的答案。对于每一个字符 \(\textit{s[i]}\)，如果 \(i \lt 2\) 或者 \(s[i]\) 与 \(s[i - 1]\) 不等，或者 \(s[i]\) 与 \(s[i - 2]\) 不等，我们就将 \(s[i]\) 添加到 \(\textit{ans}\) 中。

最后，我们将 \(\textit{ans}\) 中的字符连接起来，就得到了答案。

时间复杂度 \(O(n)\)，其中 \(n\) 为字符串 \(s\) 的长度。忽略答案的空间消耗，空间复杂度 \(O(1)\)。

Python3JavaC++GoTypeScriptJavaScriptPHP

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)

class Solution {
    public String makeFancyString(String s) {
        StringBuilder ans = new StringBuilder();
        for (int i = 0; i < s.length(); ++i) {
            char c = s.charAt(i);
            if (i < 2 || c != s.charAt(i - 1) || c != s.charAt(i - 2)) {
                ans.append(c);
            }
        }
        return ans.toString();
    }
}

class Solution {
public:
    string makeFancyString(string s) {
        string ans = "";
        for (int i = 0; i < s.length(); ++i) {
            char c = s[i];
            if (i < 2 || c != s[i - 1] || c != s[i - 2]) {
                ans += c;
            }
        }
        return ans;
    }
};

func makeFancyString(s string) string {
    ans := []byte{}
    for i, ch := range s {
        if c := byte(ch); i < 2 || c != s[i-1] || c != s[i-2] {
            ans = append(ans, c)
        }
    }
    return string(ans)
}

function makeFancyString(s: string): string {
    const ans: string[] = [];
    for (let i = 0; i < s.length; ++i) {
        if (s[i] !== s[i - 1] || s[i] !== s[i - 2]) {
            ans.push(s[i]);
        }
    }
    return ans.join('');
}

/**
 * @param {string} s
 * @return {string}
 */
var makeFancyString = function (s) {
    const ans = [];
    for (let i = 0; i < s.length; ++i) {
        if (s[i] !== s[i - 1] || s[i] !== s[i - 2]) {
            ans.push(s[i]);
        }
    }
    return ans.join('');
};

class Solution {
    /**
     * @param String $s
     * @return String
     */
    function makeFancyString($s) {
        $ans = '';
        for ($i = 0; $i < strlen($s); $i++) {
            $c = $s[$i];
            if ($i < 2 || $c !== $s[$i - 1] || $c !== $s[$i - 2]) {
                $ans .= $c;
            }
        }
        return $ans;
    }
}

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

题目描述

解法

方法一：模拟

评论