Question

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

English Version

题目描述

给你一个仅由 大写 英文字符组成的字符串 s 。

你可以对此字符串执行一些操作，在每一步操作中，你可以从 s 中删除 任一个 "AB" 或 "CD" 子字符串。

通过执行操作，删除所有 "AB" 和 "CD" 子串，返回可获得的最终字符串的 最小 可能长度。

注意，删除子串后，重新连接出的字符串可能会产生新的 "AB" 或 "CD" 子串。

 

示例 1：

输入：s = "ABFCACDB"
输出：2
解释：你可以执行下述操作：
- 从 "_AB_FCACDB" 中删除子串 "AB"，得到 s = "FCACDB" 。
- 从 "FCA_CD_B" 中删除子串 "CD"，得到 s = "FCAB" 。
- 从 "FC_AB_" 中删除子串 "AB"，得到 s = "FC" 。
最终字符串的长度为 2 。
可以证明 2 是可获得的最小长度。

示例 2：

输入：s = "ACBBD"
输出：5
解释：无法执行操作，字符串长度不变。

 

提示：

• 1 <= s.length <= 100
• s 仅由大写英文字母组成

解法

方法一：栈

我们遍历字符串 $s$，对于当前遍历到的字符 $c$，如果栈不为空且栈顶元素 $top$ 与 $c$ 可以组成 $AB$ 或 $CD$，则弹出栈顶元素，否则将 $c$ 入栈。

最后栈中剩余的元素个数就是最终字符串的长度。

在实现上，我们可以在栈中预先放入一个空字符，这样就不需要在遍历字符串时判断栈是否为空了，最后返回栈的大小减一即可。

时间复杂度 $O(n)$，空间复杂度 $O(n)$。其中 $n$ 是字符串 $s$ 的长度。

class Solution:
  def minLength(self, s: str) -> int:
    stk = [""]
    for c in s:
      if (c == "B" and stk[-1] == "A") or (c == "D" and stk[-1] == "C"):
        stk.pop()
      else:
        stk.append(c)
    return len(stk) - 1

class Solution {
  public int minLength(String s) {
    Deque<Character> stk = new ArrayDeque<>();
    stk.push(' ');
    for (char c : s.toCharArray()) {
      if ((c == 'B' && stk.peek() == 'A') || (c == 'D' && stk.peek() == 'C')) {
        stk.pop();
      } else {
        stk.push(c);
      }
    }
    return stk.size() - 1;
  }
}

class Solution {
public:
  int minLength(string s) {
    string stk = " ";
    for (char& c : s) {
      if ((c == 'B' && stk.back() == 'A') || (c == 'D' && stk.back() == 'C')) {
        stk.pop_back();
      } else {
        stk.push_back(c);
      }
    }
    return stk.size() - 1;
  }
};

func minLength(s string) int {
  stk := []byte{' '}
  for _, c := range s {
    if (c == 'B' && stk[len(stk)-1] == 'A') || (c == 'D' && stk[len(stk)-1] == 'C') {
      stk = stk[:len(stk)-1]
    } else {
      stk = append(stk, byte(c))
    }
  }
  return len(stk) - 1
}

function minLength(s: string): number {
  const stk: string[] = [''];
  for (const c of s) {
    if (c === 'B' && stk.at(-1)! === 'A') {
      stk.pop();
    } else if (c === 'D' && stk.at(-1)! === 'C') {
      stk.pop();
    } else {
      stk.push(c);
    }
  }
  return stk.length - 1;
}

impl Solution {
  pub fn min_length(s: String) -> i32 {
    let mut ans: Vec<u8> = Vec::new();

    for c in s.bytes() {
      if let Some(last) = ans.last() {
        if *last == b'A' && c == b'B' {
          ans.pop();
        } else if *last == b'C' && c == b'D' {
          ans.pop();
        } else {
          ans.push(c);
        }
      } else {
        ans.push(c);
      }
    }

    ans.len() as i32
  }
}