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

English Version

题目描述

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

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

解法

方法一：模拟

我们可以遍历字符串 $s$，并使用一个数组 $\textit{ans}$ 记录当前的答案。对于每一个字符 $c$，如果 $\textit{ans}$ 的长度小于 $2$ 或者 $\textit{ans}$ 的最后两个字符不等于 $c$，我们就将 $c$ 添加到 $\textit{ans}$ 中。

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

时间复杂度 $O(n)$，空间复杂度 $O(n)$。其中 $n$ 为字符串 $s$ 的长度。

Python3

class Solution:
    def makeFancyString(self, s: str) -> str:
        ans = []
        for c in s:
            if len(ans) < 2 or ans[-1] != c or ans[-2] != c:
                ans.append(c)
        return "".join(ans)

Java

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

C++

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

Go

func makeFancyString(s string) string {
	ans := []rune{}
	for _, c := range s {
		if n := len(ans); n < 2 || c != ans[n-1] || c != ans[n-2] {
			ans = append(ans, c)
		}
	}
	return string(ans)
}

TypeScript

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

JavaScript

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

PHP

class Solution {
    /**
     * @param String $s
     * @return String
     */
    function makeFancyString($s) {
        $ans = [];
        $length = strlen($s);

        for ($i = 0; $i < $length; $i++) {
            $n = count($ans);
            if ($n < 2 || $s[$i] !== $ans[$n - 1] || $s[$i] !== $ans[$n - 2]) {
                $ans[] = $s[$i];
            }
        }

        return implode('', $ans);
    }
}