字符串消消乐

字符串消消乐是一种常见的游戏。游戏规则如下：

给定一个字符串，每次可以选择任意两个相邻的字符，并将其删除，删除后剩下的字符串重新拼接在一起。重复操作直到无法继续删除。

例如，给定字符串 "abccba"，可以首先删除 "cc"，剩下 "abbba"，然后删除 "bb"，再剩下 "aaa"，无法继续删除，游戏结束。

请问，给定一个字符串，最终剩下的字符串是什么？

例如，给定字符串 "cababa"，最终剩下的字符串为 "cb"。

实现该游戏的算法可以使用栈。具体步骤如下：

1. 创建一个栈，将字符串中的每个字符依次压入栈中。
2. 从栈顶开始遍历栈中的每个字符，如果当前字符和下一个字符相同，则弹出这两个字符；否则继续遍历下一个字符。
3. 将栈中剩余的字符取出并拼接起来，即为最终剩下的字符串。

下面是用 Python 实现该算法的代码示例：

def removeAdjacentDuplicates(s: str) -> str:
    stack = []
    for c in s:
        if stack and stack[-1] == c:
            stack.pop()
        else:
            stack.append(c)
    return ''.join(stack)

使用该函数可以解决上述问题：

s = "cababa"
result = removeAdjacentDuplicates(s)
print(result)  # 输出 "cb"