难度: Easy
给出由小写字母组成的字符串 S，重复项删除操作会选择两个相邻且相同的字母，并删除它们。
在 S 上反复执行重复项删除操作，直到无法继续删除。
在完成所有重复项删除操作后返回最终的字符串。答案保证唯一。
示例：
输入："abbaca" 输出："ca" 解释： 例如，在 "abbaca" 中，我们可以删除 "bb" 由于两字母相邻且相同，这是此时唯一可以执行删除操作的重复项。之后我们得到字符串 "aaca"，其中又只有 "aa" 可以执行重复项删除操作，所以最后的字符串为 "ca"。
提示：
1 <= S.length <= 20000S 仅由小写英文字母组成。运行时间: 38 ms
内存: 16.8 MB
class Solution:
def removeDuplicates(self, s: str) -> str:
stack = list()
for alpha in s:
if stack and stack[-1]==alpha:
stack.pop()
else:
stack.append(alpha)
return "".join(stack)
# stk = list()
# for ch in s:
# if stk and stk[-1] == ch:
# stk.pop()
# else:
# stk.append(ch)
# return "".join(stk)
这个题解采用了栈的数据结构来处理问题。遍历字符串中的每个字符，使用栈来暂存字符。如果栈顶的字符和当前遍历到的字符相同，则弹出栈顶字符（相当于删除两个相邻的相同字符）。如果不同，则将当前字符压入栈。这样，遍历完整个字符串后，栈中剩余的字符顺序就是删除所有相邻重复项后的结果。最后，将栈中的字符连接成字符串作为结果返回。
时间复杂度: O(n)
空间复杂度: O(n)
# 定义Solution类
class Solution:
# 定义移除重复字符的方法
def removeDuplicates(self, s: str) -> str:
stack = [] # 创建一个空栈用于存储字符
# 遍历输入字符串中的每个字符
for alpha in s:
if stack and stack[-1] == alpha: # 如果栈不为空且栈顶字符与当前字符相同
stack.pop() # 弹出栈顶字符
else:
stack.append(alpha) # 否则将当前字符压入栈
return ''.join(stack) # 将栈中的字符连接成字符串返回
栈是一种后进先出（LIFO）的数据结构，这使得它在处理类似删除相邻重复项的问题时非常有效。当处理字符串时，遇到与栈顶相同的字符，可以立即将栈顶元素弹出，这样可以方便地撤销前一步的操作，与问题要求的连续消除动作直接对应。如果使用队列（先进先出），则需要访问整个数据结构来找到需要删除的元素，效率较低。链表虽然可以从任何位置增加或删除元素，但在这种具体问题中，需要额外的指针操作和遍历，不如直接使用栈来得直接和高效。
这种方法同样适用于处理字符串中间的连续重复字符。以'abba'为例，处理过程如下：字符'a'被推入栈，接着'b'被推入栈，再次遇到'b'时，发现栈顶元素也是'b'，因此弹栈。之后，字符'a'进栈，与栈顶的'a'相同，再次弹栈。最终栈为空，表示所有连续重复的字符都被有效删除。
总操作次数最多为2n，但实际上可能少于这个数。每个字符最多被推入栈一次和从栈中弹出一次。然而，并不是所有字符都会发生弹栈操作。只有当当前字符与栈顶字符相同时才会弹栈，因此实际操作数取决于输入字符串中相邻重复字符的分布情况。如果字符串中没有任何相邻的重复字符，那么只有n次推入操作，没有弹出操作。
在实际应用中，这种方法的时间复杂度是O(n)，其中n是字符串的长度，这意味着它可以有效地处理长度较大的字符串。尽管栈操作涉及到频繁的推入和弹出，但每个操作的时间复杂度都是O(1)，因此总体上是高效的。然而，如果栈的实现不当或者在极端情况下（如极大的字符串或特殊的硬件限制），可能会有性能瓶颈，比如内存消耗过大。在大多数标准应用场景中，这种方法是有效且性能是可接受的。