【Py/Java/C++三种语言详解】LeetCode每日一题240110【栈】LeetCode2696、删除子串后的字符串最小长度

题目链接

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

题目描述

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

解题思路

非常典型的消消乐类型栈题，类似题目包括LeetCode20、有效的括号，LeetCode1047、删除字符串中所有相邻重复项 。

维护一个栈，然后遍历s中的所有字符ch，考虑几种情况。当

• ch是"B"且栈顶元素为"A"的情况，删除这对"AB"，即弹出栈顶的"A"，当前"B"无需入栈
• ch是"D"且栈顶元素为"C"的情况，删除这对"CD"，即弹出栈顶的"C"，当前"D"无需入栈
• 其余情况，没有出栈操作，元素直接入栈。

思考：如果可以构成的配对不止"AB"、"CD"，还包括"EF"、"GH"、…、"YZ"等更多组配对，那么应该如何修改代码？

代码

Python

# 字符串消消乐类型题目：经典栈应用题
# 时间复杂度O(N)，空间复杂度O(N)
# 相关题目：
# LeetCode20.有效的括号
# LeetCode1047. 删除字符串中的所有相邻重复项
class Solution:
    def minLength(self, s: str) -> int:
        # 初始化一个栈
        stack = list()
        # 遍历s中的每一个元素ch
        for ch in s:
            # ch是"B"且栈顶元素为"A"的情况，删除这对"AB"
            if ch == "B" and stack and stack[-1] == "A":
                    stack.pop()
            # ch是"D"且栈顶元素为"C"的情况，删除这对"cd"
            elif ch == "D" and stack and stack[-1] == "C":
                    stack.pop()
            # 其余情况，元素都需要入栈
            else:
                stack.append(ch)
        # 最终返回栈的长度，即为删除后所剩余的字符串长度
        return len(stack)

Java

public class Solution {
    public int minLength(String s) {
        Stack<Character> stack = new Stack<>();
        
        for (char ch : s.toCharArray()) {
            if (ch == 'B' && !stack.isEmpty() && stack.peek() == 'A') {
                stack.pop();
            } else if (ch == 'D' && !stack.isEmpty() && stack.peek() == 'C') {
                stack.pop();
            } else {
                stack.push(ch);
            }
        }
        
        return stack.size();
    }
}

C++

class Solution {
public:
    int minLength(string s) {
        stack<char> st;
        
        for (char ch : s) {
            if (ch == 'B' && !st.empty() && st.top() == 'A') {
                st.pop();
            } else if (ch == 'D' && !st.empty() && st.top() == 'C') {
                st.pop();
            } else {
                st.push(ch);
            }
        }
        
        return st.size();
    }
};

时空复杂度

时间复杂度：O(N)。仅需一次遍历字符串s

空间复杂度：O(M)。栈所占空间。

---

华为OD算法/大厂面试高频题算法练习冲刺训练

• 华为OD算法/大厂面试高频题算法冲刺训练目前开始常态化报名！目前已服务100+同学成功上岸！

• 课程讲师为全网50w+粉丝编程博主@吴师兄学算法 以及小红书头部编程博主@闭着眼睛学数理化

• 每期人数维持在20人内，保证能够最大限度地满足到每一个同学的需求，达到和1v1同样的学习效果！

• 60+天陪伴式学习，40+直播课时，300+动画图解视频，300+LeetCode经典题，200+华为OD真题/大厂真题，还有简历修改、模拟面试、专属HR对接将为你解锁

• 可上全网独家的欧弟OJ系统练习华子OD、大厂真题

• 可查看链接 大厂真题汇总 & OD真题汇总(持续更新)

• 绿色聊天软件戳 od1336了解更多