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

🟢   🔖  栈 字符串 模拟  🔗 力扣 LeetCode

题目

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 " AB FCACDB", so s = "FCACDB".
• Remove the substring "FCA CD B", so s = "FCAB".
• Remove the substring "FC AB ", 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" 子串。

解题思路

1. 模拟移除过程：
   对于每次操作，我们需要查找并移除 "AB" 或 "CD"，这样在移除这些特定子串后，字符串会自动合并，形成新的字符串。这个过程可能导致出现新的可移除子串。因此，我们需要一直重复操作，直到再也无法找到 "AB" 或 "CD"。

2. 使用栈优化操作：
   使用栈来模拟这个过程。具体做法是从左到右遍历字符串的每个字符，将字符压入栈中，每次压入后检查栈顶的两个字符是否形成 "AB" 或 "CD"。如果形成，就将这两个字符弹出栈，模拟移除它们。这样，栈中的字符就是剩余未能被移除的部分。

3. 最终结果：
   遍历完成后，栈中的元素就是无法继续移除的字符，栈的长度就是最后剩下字符串的最小长度。

复杂度分析

• 时间复杂度：O(n)，其中 n 是字符串的长度。我们只需遍历字符串一次，对于每个字符，压栈和弹栈的操作都是常数时间。
• 空间复杂度：O(n)，最坏情况下，栈中会保留所有字符，因此需要 O(n) 的额外空间。

代码

/**
 * @param {string} s
 * @return {number}
 */
var minLength = function (s) {
	let stack = [];

	for (let char of s) {
		stack.push(char);

		// 检查栈顶的两个字符是否形成 "AB" 或 "CD"
		if (stack.length >= 2) {
			let lastTwo = stack[stack.length - 2] + stack[stack.length - 1];

			// 如果发现 "AB" 或 "CD"，则弹出这两个字符
			if (lastTwo === 'AB' || lastTwo === 'CD') {
				stack.pop(); // 移除栈顶字符
				stack.pop(); // 再移除栈顶字符
			}
		}
	}

	return stack.length; // 栈中剩余的字符就是最终字符串
};