LeetCode 2696. 删除子串后的字符串最小长度

一、题目

1、题目描述

给你一个仅由?大写?英文字符组成的字符串?s?。

你可以对此字符串执行一些操作，在每一步操作中，你可以从?s?中删除?任一个?"AB"?或?"CD"?子字符串。

通过执行操作，删除所有?"AB"?和?"CD"?子串，返回可获得的最终字符串的?最小?可能长度。

注意，删除子串后，重新连接出的字符串可能会产生新的?"AB"?或?"CD"?子串。

2、接口描述

?

class Solution {
public:
    int minLength(string s) {
        
    }
};

3、原题链接

2696. 删除子串后的字符串最小长度

二、解题报告

1、思路分析

当成括号匹配问题即可，一次遍历维护一个栈，和栈顶配对就记录

2、复杂度

时间复杂度： O(N) 空间复杂度：O(N)

3、代码详解

?

class Solution {
public:
    int minLength(string s) {
        stack<char> st;
        int ret = s.size();
        for(auto x : s)
        {
            if(st.size() && x == 'B' && st.top() == 'A')
                ret -= 2 , st.pop();
            else if(st.size() && x == 'D' && st.top() == 'C')
                ret -= 2 , st.pop();
            else
                st.push(x);
        }
        return ret;
    }
};