题目描述
给你一个仅由 大写 英文字符组成的字符串 s
。
你可以对此字符串执行一些操作,在每一步操作中,你可以从 s
中删除 任一个 "AB"
或 "CD"
子字符串。
通过执行操作,删除所有 "AB"
和 "CD"
子串,返回可获得的最终字符串的 最小 可能长度。
注意,删除子串后,重新连接出的字符串可能会产生新的 "AB"
或 "CD"
子串。
样例
输入:s = "ABFCACDB"
输出:2
解释:你可以执行下述操作:
- 从 "ABFCACDB" 中删除子串 "AB",得到 s = "FCACDB"。
- 从 "FCACDB" 中删除子串 "CD",得到 s = "FCAB"。
- 从 "FCAB" 中删除子串 "AB",得到 s = "FC"。
最终字符串的长度为 2。
可以证明 2 是可获得的最小长度。
输入:s = "ACBBD"
输出:5
解释:无法执行操作,字符串长度不变。
限制
1 <= s.length <= 100
s
仅由大写英文字母组成。
算法
(栈) $O(n)$
- 使用栈模拟过程,如果栈顶是
A
且当前字符为B
,或栈顶为C
且当前字符为D
,则栈顶出栈。否则当前字符进栈。 - 最终返回栈的大小。
时间复杂度
- 每个字符最多进栈一次出栈一次,故时间复杂度为 $O(n)$。
空间复杂度
- 可以直接在原字符串上通过双指针模拟栈,故空间复杂度为常数。
C++ 代码
class Solution {
private:
inline bool judge(char a, char b) {
return (a == 'A' && b == 'B') || (a == 'C' && b == 'D');
}
public:
int minLength(string s) {
const int n = s.size();
int i = 1, j = 1;
while (j < n) {
if (i > 0 && judge(s[i - 1], s[j])) --i;
else s[i++] = s[j];
++j;
}
return i;
}
};