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

本文主要是介绍【Py/Java/C++三种语言详解】LeetCode每日一题240110【栈】LeetCode2696、删除子串后的字符串最小长度，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

文章目录

题目链接
题目描述
解题思路
代码
- Python
- Java
- C++
- 时空复杂度
华为OD算法/大厂面试高频题算法练习冲刺训练

题目链接

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中的每一个元素chfor 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了解更多