标签: 字符串
难度: 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 <= 105s 只包含小写英文字母。运行时间: 165 ms
内存: 17.5 MB
class Solution:
def makeFancyString(self, s: str) -> str:
cur = ""
cnt = 0
li = []
for c in s:
if c==cur:
if cnt<2:
cnt+=1
li.append(c)
else:
cnt = 1
cur = c
li.append(c)
return "".join(li)
该题解的主要思路是遍历字符串's'，使用一个列表'li'来构建结果字符串。通过使用变量'cur'来记录当前正在处理的字符，以及'cnt'来计数当前字符连续出现的次数。如果当前字符与'cur'相同且'cnt'小于2，字符被添加到'li'中，并且'cnt'增加。如果当前字符不同于'cur'，则更新'cur'和重置'cnt'为1，并将新字符添加到'li'中。这样就能保证构建的结果中任何字符的连续出现次数不会超过2，从而保证结果字符串是一个好字符串。
时间复杂度: O(n)
空间复杂度: O(n)
class Solution:
def makeFancyString(self, s: str) -> str:
cur = "" # 当前正在处理的字符
cnt = 0 # 当前字符的连续出现次数
li = [] # 结果字符串构建的列表
for c in s: # 遍历输入字符串
if c == cur: # 如果字符未变
if cnt < 2: # 如果连续出现次数少于2
cnt += 1 # 增加计数
li.append(c) # 添加到结果列表
else: # 如果字符变了
cnt = 1 # 重置计数为1
cur = c # 更新当前字符
li.append(c) # 添加新字符到结果列表
return "".join(li) # 将列表转换为字符串并返回
在给出的算法中，如果输入字符串为空，即`s`是一个空字符串，则循环不会执行，因为没有字符可遍历。由于列表`li`是空的，`"".join(li)`将返回一个空字符串。因此，即使输入为空，函数也能正确返回一个空字符串，符合预期结果。
算法通过变量`cnt`来控制连续字符的添加。每次遇到新字符时，会重置`cnt`为1，并更新`cur`为当前字符，这样确保了每当字符变化时，计数器重新开始。若字符未改变且`cnt`已小于2，则`cnt`自增并添加字符。这样，即便是在字符边界转换时，由于`cnt`和`cur`的及时更新，可以保证任何字符连续出现的次数不会超过2次。
选择2作为连续出现次数的上限是基于题目要求，题目可能规定了最多允许连续出现同一字符两次来定义一个好字符串。这是基于题目的具体规则来设定的，若题目要求不同，连续出现次数的上限也会相应调整。
该算法的时间复杂度为O(n)，其中n是输入字符串的长度，因为每个字符只被遍历一次。空间复杂度也为O(n)，因为在最坏的情况下（例如每两个字符就变化一次），结果字符串`li`可能接近原字符串长度。虽然算法在处理非常长的字符串时会占用较多内存，但整体上看，这是线性时间和空间复杂度，通常被认为是效率较高的。不过，如果`li`的长度成为问题或者内存有限制，可能需要考虑更优化的存储方法或在其他方面进行调整。