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

🟢   🔖  字符串  🔗 力扣 LeetCode

题目

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 = "le e etcode"

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 = "a aab aa aa"

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 <= 10^5
• 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 <= 10^5
• s 只包含小写英文字母。

解题思路

1. 初始化变量：

   • 使用 res 来存储结果字符串。
   • 使用 sameCount 记录当前字符出现的次数。
   • 使用 curChar 来跟踪当前正在处理的字符。

2. 遍历字符串：

   • 对于字符串中的每个字符，检查它是否与 curChar 相同：
     • 如果相同，则增加 sameCount。
     • 如果不同，则将 curChar 更新为当前字符，并将 sameCount 重置为 1。
   • 如果 sameCount 小于 3，表示当前字符可以添加到结果中，则将其添加到 res。

3. 返回结果：

   • 最后返回构建的字符串 res。

复杂度分析

• 时间复杂度：O(n)，其中 n 是字符串 s 的长度，只遍历一次字符串，每个字符的处理是常数时间。
• 空间复杂度：O(n)，用于存储结果字符串，最坏情况下（输入字符串中没有重复字符），res 字符串的长度与输入字符串相同。

代码

var makeFancyString = function (s) {
	let res = '',
		sameCount = 0,
		curChar;
	for (let char of s) {
		if (curChar == char) {
			sameCount++;
		} else {
			curChar = char;
			sameCount = 1;
		}
		if (sameCount < 3) {
			res += char;
		}
	}
	return res;
};

相关题目

题号	标题	题解	标签	难度
3316	从原字符串里进行删除操作的最多次数		数组 哈希表 双指针 2+