给你一个仅由 大写 英文字符组成的字符串 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 仅由大写英文字母组成

分析

        题目要求通过删除任意一个 "AB" 或 "CD" 子字符串，得到最后最短可能的字符串长度。由于被删除的子字符串是固定的，因此每次只需要检查当前字符串中是否存在这些子字符串，并且如果存在就删除。我们可以通过利用栈这种数据结构实现这个过程，栈在处理相邻字符匹配的情况下非常高效，因为栈是后进先出 (LIFO) 的数据结构。

详细分析步骤：

1. 初始化栈：

   • 使用一个空栈来存放字符。

2. 遍历字符串：

   • 遍历字符串 s 中的每一个字符。

3. 检查相邻字符：

   • 在遍历时，检查栈顶字符和当前遍历字符是否可以组成 "AB" 或 "CD" 子字符串。
     • 如果栈顶字符与当前字符能组成 "AB" 或 "CD"，说明这些字符可以被删除。
     • 使用 stack.pop() 处理这种情况，即删除栈顶字符，相当于删除子串中的其中一个字符，当前字符也就被忽略。
     • 如果不能组成 "AB" 或 "CD"，则将当前字符放入栈中。

4. 计算最终结果：

   • 遍历结束，栈中剩余的字符即是无法再被删除的字符。
   • 栈中字符的数量就是最终的字符串长度。

流程图

开始
↓
初始化一个空栈
↓
遍历字符串中的每一个字符
↓
检查栈顶字符和当前字符是否可以形成 "AB" 或 "CD"
↓
是 ——> 弹出栈顶字符
↓
否 ——> 将当前字符入栈
↓
遍历结束
↓
栈中剩余字符的数量即为最终字符串的最小长度
↓
结束

代码讲解

class Solution {
    public int minLength(String s) {
        // 创建一个栈来存放字符
        Stack<Character> stack = new Stack<>();
        
        // 遍历字符串中的每一个字符
        for (char c : s.toCharArray()) {
            // 检查栈顶字符和当前字符是否可以形成 "AB" 或 "CD"
            if (!stack.isEmpty() && 
                ((stack.peek() == 'A' && c == 'B') || (stack.peek() == 'C' && c == 'D'))) {
                stack.pop(); // 如果是，则移除栈顶字符
            } else {
                stack.push(c); // 否则，将当前字符入栈
            }
        }
        
        // 栈中的剩余字符数量即为最终字符串的最小可能长度
        return stack.size();
    }
}

讲解

• 初始化栈：

   Stack<Character> stack = new Stack<>();

• 创建一个空的栈对象，用于存放字符。
• 遍历字符串：

   for (char c : s.toCharArray()) {

• 使用增强 for 循环将字符串 s 转成字符数组并逐个遍历字符。
• 检查相邻字符：

   if (!stack.isEmpty() && 
       ((stack.peek() == 'A' && c == 'B') || (stack.peek() == 'C' && c == 'D'))) {
       stack.pop();
   } else {
       stack.push(c);
   }

• 使用 !stack.isEmpty() 检查栈是否非空。
• 使用 stack.peek() 获取栈顶字符，并检查当前字符 c 和栈顶字符是否匹配可构成 "AB" 或 "CD" 对。
  • 如果匹配：

       stack.pop();

删除栈顶字符，因为构成了 "AB" 或 "CD"。

• 如果不匹配：

       stack.push(c);

将当前字符加入栈中。

• 计算结果：

   return stack.size();

• 遍历结束后，栈中剩下的字符数量即为最终字符串的最小可能长度。

知识点解析

• 栈 (Stack)：

  • 栈是一种后进先出 (LIFO: Last In, First Out) 的数据结构。在这里，我们利用栈的这一特性来匹配相邻的字符，方便地处理 "AB" 和 "CD" 子串的删除操作。

• 字符串遍历：

  • 代码中的 for (char c : s.toCharArray()) 是一种常见的逐字符遍历字符串的方法。

• 条件判断：

  • 利用条件判断 if (!stack.isEmpty() && ((stack.peek() == 'A' && c == 'B') || (stack.peek() == 'C' && c == 'D')))，我们可以高效地匹配和删除满足条件的子串。