🔗 🟢 2696. Minimum String Length After Removing Substrings 1282

tags: Weekly Contest 346 字串(String) 堆疊(Stack) 模擬(Simulation)

題意

給定一個只包含 大寫 英文字母的字串 ss。

你可以對這個字串進行一些操作，每次操作中，你可以移除字串中的 任意 一個子字串 "AB" 或 "CD"。

返回你能得到的結果字串的 最小 可能長度。

注意 當移除子字串後，字串會重新連接，可能會產生新的 "AB" 或 "CD" 子字串。

思路：堆疊(Stack)

注意到題目敘述最後一句，由於我們需要反覆移除字串中的 "AB" 或 "CD" 子字串，若要在一次遍歷中完成，我們可以採用 堆疊(Stack) 的方法，利用其後入先出的特性，在遍歷字串的過程中，將字符逐個壓入堆疊，並在適當的時候彈出堆疊頂部的字符，實現移除操作。

具體步驟如下：

  1. 初始化堆疊：創建一個空的堆疊 stst，用於存儲尚未被移除的字符。
  2. 逐字符遍歷字串：從左到右依次遍歷字串中的每一個字符。
  3. 檢查可替換的子字串：
    • 對於當前字符 ch，檢查堆疊頂部的字符 st[-1]。
    • 如果 st[-1] 與 ch 組成 "AB" 或 "CD"，則這是一個可以被移除的子字串。我們可以通過 彈出堆疊頂部的字符 來實現移除操作，不將當前字符壓入堆疊。
    • 否則，將當前字符壓入堆疊中，表示這個字符暫時無法與後續字符組成可移除的子字串。

最終，堆疊中剩下的字符數量就是最短可能的字串長度。

複雜度分析

  • 時間複雜度：O(n)\mathcal{O}(n)，其中 nn 是字串 ss 的長度。我們需要遍歷字串 ss 一次，每個字符最多被壓入和彈出堆疊一次。
  • 空間複雜度：O(n)\mathcal{O}(n)，在最壞的情況下（沒有可移除的子字串），堆疊可能需要存儲整個字串。
1
2
3
4
5
6
7
8
9
class Solution:
    def minLength(self, s: str) -> int:
        st = []
        for ch in s:
            if len(st) and (st[-1] == "A" and ch == "B" or st[-1] == "C" and ch == "D"):
                st.pop()
            else:
                st.append(ch)
        return len(st)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    int minLength(string s) {
        stack<char> st;
        for (char ch : s) {
            if (st.size() && (st.top() == 'A' && ch == 'B' ||
                              st.top() == 'C' && ch == 'D')) {
                st.pop();
            } else {
                st.push(ch);
            }
        }
        return st.size();
    }
};

寫在最後

PROMPT

masterpiece, best quality, high quality, extremely detailed CG unity 8k wallpaper, extremely detailed, High Detail, vibrant colors, backlight, photo background,

(1girl, solo), long hair, (black eyes), looking at viewer, (standing), full body, black hair, school uniform, short sleeves, pleated skirt, skirt, shirt, (green top, green shirt), black bottom, (black skirt), serafuku, socks, looking back, indoors, sailor collar, black footwear, window, white socks, hallway,

A girl in a green shirt and black pleated skirt standing, in a long school hallway, windows and doors on both sides, bright natural light coming through the windows, serene atmosphere, looking back at the camera,