难度: Easy
给你一个仅由 大写 英文字符组成的字符串 s 。
你可以对此字符串执行一些操作，在每一步操作中，你可以从 s 中删除 任一个 "AB" 或 "CD" 子字符串。
通过执行操作，删除所有 "AB" 和 "CD" 子串，返回可获得的最终字符串的 最小 可能长度。
注意，删除子串后，重新连接出的字符串可能会产生新的 "AB" 或 "CD" 子串。
示例 1：
输入：s = "ABFCACDB" 输出：2 解释：你可以执行下述操作： - 从 "ABFCACDB" 中删除子串 "AB"，得到 s = "FCACDB" 。 - 从 "FCACDB" 中删除子串 "CD"，得到 s = "FCAB" 。 - 从 "FCAB" 中删除子串 "AB"，得到 s = "FC" 。 最终字符串的长度为 2 。 可以证明 2 是可获得的最小长度。
示例 2：
输入：s = "ACBBD" 输出：5 解释：无法执行操作，字符串长度不变。
提示：
1 <= s.length <= 100s 仅由大写英文字母组成运行时间: 24 ms
内存: 16.5 MB
class Solution:
def minLength(self, s: str) -> int:
lst=[]
for si in s:
if len(lst)>0 and ((si =='B' and lst[-1]=='A') or (si =='D' and lst[-1]=='C')):
lst.pop(-1)
continue
lst.append(si)
return len(lst)
题解的核心思想是利用栈的数据结构来处理字符串中的"AB"和"CD"子串的删除问题。遍历字符串中的每个字符，使用栈来保存当前未被删除的字符。对于每个遍历到的字符，若当前字符和栈顶字符组成"AB"或"CD"子串，则将栈顶字符弹出，从而实现删除操作。如果不形成这样的子串，则将字符压入栈中。最后，栈中剩余的字符数就是删除所有"AB"和"CD"子串后的字符串长度。
时间复杂度: O(n)
空间复杂度: O(n)
class Solution:
def minLength(self, s: str) -> int:
lst=[] # 创建一个空列表用作栈
for si in s: # 遍历字符串中的每个字符
if len(lst)>0 and ((si =='B' and lst[-1]=='A') or (si =='D' and lst[-1]=='C')): # 检查当前字符与栈顶字符是否形成'AB'或'CD'
lst.pop(-1) # 如果是，弹出栈顶字符，相当于删除了子串
continue
lst.append(si) # 否则，将当前字符压入栈中
return len(lst) # 返回栈的大小，即最终字符串的长度
在处理具有特定模式匹配和即时删除需求的字符串问题时，栈提供了一种有效的方式来过滤和处理这些模式。当检测到特定的字符序列（如'AB'或'CD'）时，可以通过简单地弹出栈顶元素来立即删除这些序列，而不需要重构或扫描整个字符串。这种方法不仅简洁，而且效率高，因为它只需要一次遍历字符串，即O(n)的时间复杂度。
是的，该方法确保了所有可删除的'AB'和'CD'都被删除。因为每次插入一个新字符时，算法都会检查这个新字符和栈顶字符是否形成可删除的子串，如果形成，则立即进行弹栈操作。这一过程会持续到不再形成可删除的子串为止。因此，只要有可能形成'AB'或'CD'，它们就会被立即删除。
当处理类似'ABAB'或'CDCD'这样的连续子串时，每次插入字符并检测到匹配的'AB'或'CD'时，都会进行一次弹栈操作。例如，在处理'ABAB'时，首先'AB'被检测并删除（即栈弹出'A'），留下空栈；然后下一个'A'被压栈，接着'B'被压栈并再次与栈顶的'A'形成'AB'，再次弹栈。这样，每当形成可删除的子串时，它们都会被立即删除，即使是在连续情况下。
如果输入字符串s为空，该算法仍然有效且不需要特殊处理。算法开始时创建了一个空栈，然后尝试遍历字符串s中的字符。如果s为空，循环体内的代码不会执行，因此栈仍然为空。最后返回栈的长度，也就是0，恰当地反映了空字符串的长度。