050 · Make The String Great

algorithm

Published

July 2, 2026

My First Thoughts

这和上一题有些类似的。

之前一题是说：相邻的字符如果相同，就删掉。现在这一题换成：相邻的字符如果是同一个字母，但是大小写匹配成一对，也删掉。

道理是一样的。

本质上都是一种配对关系，key和value。关系可以有很多种：

key 和 value 相等
key 和 value 是同一个字母的大小写
甚至可以衍生到 1 对 a，2 对 b

就像有一个密码本，规定什么和什么能配成一对。

也可以想成一个待审核的排队清单。一个活动里，一群人排队，入场要求只有一个：需要两个人位置相邻，而且这两个人要满足某种关系。这个关系可以是同名同姓，也可以是情侣，也可以是别的规则。

放到这道题里，关系就是：

两个相邻字符是同一个字母，但是一个大写、一个小写。

所以可以维护一个 wait_list。

每来一个新字符 char，就看它能不能和当前排队清单最后一个字符配成一对：

如果能配成一对，就把清单最后一个字符移走，当前字符也不加入
如果不能配成一对，当前字符就加入清单

最开始的代码大概是：

wait_list = []

for char in s:
    if wait_list and char != wait_list[-1] and char.lower() == wait_list[-1].lower():
        wait_list.pop()
    else:
        wait_list.append(char)

return "".join(wait_list)

Why That Is Not Enough

上面的想法已经够了。

真正需要确认的是这个条件本身：

wait_list 非空 并且 当前字符不是最后一个字符 并且 当前字符小写后等于最后一个字符小写后

写成代码就是：

if wait_list and char != wait_list[-1] and char.lower() == wait_list[-1].lower():

它准确表达了“不好”的相邻字符：同一个字母，但大小写不同。

Final Idea

继续使用 wait_list 这个排队清单。

它表示：当前已经处理过的字符里，还没有被配对删除的部分。

每次读取一个新字符 char：

如果 wait_list 不为空，并且 char 可以和 wait_list 最后一个字符配成“不好”的一对，就删除 wait_list 最后一个字符
否则，把 char 加入 wait_list

判断“不好”的一对，需要同时满足：

char != wait_list[-1]

这保证两个字符大小写不同，比如 "a" 和 "A"。

还要满足：

char.lower() == wait_list[-1].lower()

这保证两个字符是同一个字母。

合起来就是：

if wait_list and char != wait_list[-1] and char.lower() == wait_list[-1].lower():

遍历结束后，wait_list 里剩下的字符就是最终的好字符串。

Why It Works

题目里每次删除的都是一对相邻字符。

从左到右处理字符串时，wait_list 的最后一个字符，就是当前结果里最靠右、也就是最可能和新字符形成相邻关系的字符。

如果新来的 char 和 wait_list[-1] 满足“同字母、大小写相反”，它们就是一对不好的相邻字符。此时删除 wait_list[-1]，并且不加入 char，就等于把这一对一起删掉：

wait_list.pop()

如果它们不能配对，char 暂时不会被删除，应该保留下来：

wait_list.append(char)

删除一对字符以后，前面的字符会重新成为新的结尾。后面继续处理新字符时，自然会检查新的相邻关系。

比如：

"abBAcC"

可以这样理解：

"abBAcC" -> "aAcC" -> "cC" -> ""

wait_list 每次都只需要看队尾，就能完成这些连续的相邻配对删除。

Code

def makeGood(s):
    wait_list = []

    for char in s:
        if wait_list and char != wait_list[-1] and char.lower() == wait_list[-1].lower():
            wait_list.pop()
        else:
            wait_list.append(char)

    return "".join(wait_list)

Complexity

Time	\(O(n)\) - `n` 是 `s` 的长度；每个字符只处理一次
Space	\(O(n)\) - 最坏情况下没有字符被删除，`wait_list` 会保存所有字符

Takeaway

当题目是在不断删除“相邻且满足某种配对关系”的元素时，可以维护一个等待清单。新元素只和清单最后一个元素判断能不能配对；能配对就删除最后一个，不能配对就加入清单。核心不是规则一定是什么，而是把这个配对规则清楚地写成条件。

← Quiz