【LeetCode2696】删除子串后的字符串最小长度

1、题目描述

【题目链接】
标签：栈 、字符串、模拟
难度：简单
给你一个仅由 大写 英文字符组成的字符串 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 <= 100
s 仅由大写英文字母组成

2、基本思路

?这是一道简单的字符串处理的题目，可以用栈模型上述的删除的过程即可，值得注意的是，删除子串后，重新连接出的字符串可能会产生新的 “AB” 或 “CD” 子串。

下面是利用栈对示例 1 模拟的过程：

• 初始化栈空；
• 栈空，A入栈；
• 当前元素B，与栈顶元素A，构成子串AB，A出栈；
• 栈空，F入栈；
• 当前元素C，栈顶元素F，构不成子串，C入栈；
• 当前元素A，栈顶元素C，构不成子串，A入栈；
• 当前元素C，栈顶元素A，构不成子串，C入栈；
• 当前元素D，栈顶元素C，构成子串CD，C出栈；
• 当前元素B，栈顶元素A，构成子串AB，A出栈；
• 字符串元素遍历完毕，栈中元素的长度即为答案；

3、代码实现

int minLength(string s) {
    stack<char> st;
    for(int i = 0;i<s.length();++i)
    {
        char c = s[i];
        if(st.empty())
            st.push(c);
        else
        {
            if(c=='D'&&st.top()=='C')
                st.pop();
            else if(c=='B'&&st.top()=='A')
                st.pop();
            else
                st.push(c);
        }
    }
    return st.size();    
}