[LeetCode] 2696. Minimum String Length After Removing Substrings

You are given a string s consisting only of uppercase English letters.

You can apply some operations to this string where, in one operation, you can remove any occurrence of one of the substrings “AB” or “CD” from s.

Return the minimum possible length of the resulting string that you can obtain.

Note that the string concatenates after removing the substring and could produce new “AB” or “CD” substrings.

Example 1:
Input: s = “ABFCACDB”
Output: 2
Explanation: We can do the following operations:

• Remove the substring “ABFCACDB”, so s = “FCACDB”.
• Remove the substring “FCACDB”, so s = “FCAB”.
• Remove the substring “FCAB”, so s = “FC”.
  So the resulting length of the string is 2.
  It can be shown that it is the minimum length that we can obtain.

Example 2:
Input: s = “ACBBD”
Output: 5
Explanation: We cannot do any operations on the string so the length remains the same.

Constraints:
1 <= s.length <= 100
s consists only of uppercase English letters.

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

给你一个仅由 大写 英文字符组成的字符串 s 。
你可以对此字符串执行一些操作，在每一步操作中，你可以从 s 中删除 任一个 “AB” 或 “CD” 子字符串。
通过执行操作，删除所有 “AB” 和 “CD” 子串，返回可获得的最终字符串的 最小 可能长度。
注意，删除子串后，重新连接出的字符串可能会产生新的 “AB” 或 “CD” 子串。

思路

遍历字符串中的每一个字母，将每个字母入栈。如果当前字母是 B，检查栈顶元素是否为 A，如果是则把 A 弹出；如果当前字母是 D，检查栈顶元素是否为 C，如果是则把 C 弹出。最后返回栈内元素个数。

复杂度

时间O(n)
空间O(n)

代码

Java实现

class Solution {
    public int minLength(String s) {
        Deque<Character> stack = new ArrayDeque<>();
        for (char c : s.toCharArray()) {
            if (c == 'B' && !stack.isEmpty() && stack.peekLast() == 'A') {
                stack.pollLast();
            } else if (c == 'D' && !stack.isEmpty() && stack.peekLast() == 'C') {
                stack.pollLast();
            } else {
                stack.offerLast(c);
            }
        }
        return stack.size();
    }
}