题意
给你一个仅由 大写 英文字符组成的字符串 s 。
你可以对此字符串执行一些操作，在每一步操作中，你可以从 s 中删除 任一个 "AB" 或 "CD" 子字符串。
通过执行操作，删除所有 "AB" 和 "CD" 子串，返回可获得的最终字符串的 最小 可能长度。
注意，删除子串后，重新连接出的字符串可能会产生新的 "AB" 或 "CD" 子串。
提示：
$1 <= s.length <= 100$
s 仅由大写英文字母组成
思路1
题目里字符串$s$的长度只有100，可以选择暴力的将字符串$s$中的$AB/CD$去掉，直到字符串里没有$AB/CD$
时间复杂度是$O(n^2)$
代码1
go语言实现的代码，调用strings的方法来判断
strings.Contains(s,"AB")判断字符串$s$里是否包含ABstrings.ReplaceAll(s,"AB","")将字符串$s$的所有$AB$替换为空，也就是去除$AB$func minLength(s string) int { for strings.Contains(s,"AB") || strings.Contains(s,"CD") { s = strings.ReplaceAll(s,"AB","") s = strings.ReplaceAll(s,"CD","") } return len(s) }思路2
用栈维护当前没有删除的字符，遍历字符串，- 如果当前遍历到的字符是B，并且栈顶元素为A，说明该字符入栈后可以构成$AB$的组合，需要将这两个字符都删除，即弹出栈顶元素
- 同理，如果当前遍历到的字符是D，并且栈顶元素为C，说明该字符入栈后可以构成$CD$的组合，需要将这两个字符都删除，即弹出栈顶元素
- 否则，将当前遍历到的字符入栈
最后栈的长度就是答案
时间复杂度是$O(n)$
代码2
c++代码，使用$STL$的栈$stack$
stack<char>stk定义一个char类型的栈stkstk.empty()判断栈是否为空，为空时返回truestk.top()返回栈顶元素stk.pop()弹出栈顶元素stk.push(ch)将元素ch放入栈中stk.size()返回栈的大小class Solution { public: int minLength(string s) { stack<char>stk; for(int i=0;i<s.size();i++){ char ch = s[i]; if(!stk.empty()&&((ch=='B'&&stk.top()=='A')||(ch=='D'&&stk.top()=='C'))){ stk.pop(); }else{ stk.push(ch); } } return stk.size(); } };go代码，借助数组模拟栈
因为栈是先进后出的结果，所以- 得到栈顶元素： 等价于得到数组的最后一个元素，即
stk[len(stk) - 1] - 弹出栈顶元素：等价于删除数组的最后一个元素，即
stk = stk[:len(stk) - 1] - 将元素
ch放入栈中：等价于向数组中追加元素，即stk = append(stk,ch)func minLength(s string) int { var stk []rune for _,ch := range s { lasLen := len(stk) - 1 if len(stk) > 0 && ( (ch=='B'&&stk[lasLen] == 'A') || (ch=='D'&&stk[lasLen] == 'C') ) { stk = stk[:lasLen] }else{ stk = append(stk,ch) } } return len(stk) }
