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

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

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

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

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

示例 1：

**输入：** s = "ABFCACDB"
**输出：** 2
**解释：** 你可以执行下述操作：
- 从 " _ **AB**_ FCACDB" 中删除子串 "AB"，得到 s = "FCACDB" 。
- 从 "FCA _ **CD**_ B" 中删除子串 "CD"，得到 s = "FCAB" 。
- 从 "FC ** _AB_** " 中删除子串 "AB"，得到 s = "FC" 。
最终字符串的长度为 2 。
可以证明 2 是可获得的最小长度。

示例 2：

**输入：** s = "ACBBD"
**输出：** 5
**解释：** 无法执行操作，字符串长度不变。

提示：

• 1 <= s.length <= 100
• s 仅由大写英文字母组成

题目

6439.删除子串后的字符串最小长度
{:width=400}

解题思路

可以使用栈来实现。遍历字符串s，如果当前字符不是’B’或’D’，则将其入栈；如果当前字符为’B’或’D’，则判断栈顶元素是否为’A’或’C’，如果是，则将栈顶元素出栈，否则将当前字符入栈。最终栈中剩余的元素即为无法匹配的字符，其个数即为最终字符串的长度。
初始状态：
{:width=400}
将遇到除了B，D的元素入栈，如果遇到了B元素和D元素，此时与栈顶元素，如果栈顶元素为A或者C，则弹出栈顶元素，top指针减1
知道遍历完字符串s即可，此时栈中元素的个数就是最终字符串的最小可能值
{:width=400}

代码

[]

int minLength(char * s){
    int len = strlen(s);
    char* stack = (char*)malloc(sizeof(char) * len);
    int top = -1;
    for (int i = 0; i < len; i++) {
        if (s[i] == 'B') {
            if (top >= 0 && stack[top] == 'A') {
                top--;
            } else {
                stack[++top] = s[i];
            }
        }
        else if (s[i] == 'D') {
            if (top >= 0 && stack[top] == 'C') {
                top--;
            } else {
                stack[++top] = s[i];
            }
        }
        else
            stack[++top] = s[i];
    }
    return top + 1;
}

[]

class Solution {
public:
    int minLength(string s) {
        int len = s.size();
        char* stack = (char*)malloc(sizeof(char) * len);
        int top = -1;
        for (int i = 0; i < len; i++) {
            if (s[i] == 'B') {
                if (top >= 0 && stack[top] == 'A') {
                    top--;
                } else {
                    stack[++top] = s[i];
                }
            }
            else if (s[i] == 'D') {
                if (top >= 0 && stack[top] == 'C') {
                    top--;
                } else {
                    stack[++top] = s[i];
                }
            }
            else
                stack[++top] = s[i];
        }
        return top + 1;    
    }
};

执行用时和内存消耗均100%
{:width=400}