🔗 🟡 1963. Minimum Number of Swaps to Make the String Balanced 1689

tags: `Weekly Contest 253` `字串(String)` `堆疊(Stack)` `雙指標(Two Pointers)` `貪心(Greedy)`

題意

給定一個下標從 $0$ 開始的字串 $s$ ，其長度 $n$ 為偶數，包含正好 $\frac{n}{2}$ 個開括號 '[' 和 $\frac{n}{2}$ 個閉括號 ']'。

如果一個字串滿足以下條件之一，則稱為平衡字串：

它是空字串
它可以寫成 AB 的形式，其中 A 和 B 都是平衡字串
它可以寫成 [C] 的形式，其中 C 是一個平衡字串

你可以任意次數地交換任意兩個索引處的括號。

返回 使 s 平衡的最小交換次數 。

思路：堆疊(Stack)

首先我們按照一般配對的思路，使用堆疊(Stack) 來檢查是否可以成功配對。但在無法配對時，不進行交換，而是先直接跳過。

當遇到 '[' 時，將其推入堆疊，表示一個待匹配的開括號。
當遇到 ']' 時，檢查堆疊是否有元素：
- 如果有，則表示可以匹配一個開括號，將堆疊頂部元素彈出。
- 如果沒有，則表示這是一個不平衡的閉括號，可以維護一個計數器 $cnt$ $c n t$ ，表示無法配對的閉括號數量。
  - 但由於題目保證了正好有 $\frac{n}{2}$ 個開括號和 $\frac{n}{2}$ 個閉括號，所以最後堆疊的大小就是無法配對的閉括號數量。

等到遍歷完所有字串後，堆疊的大小就是無法配對的括號對數。將可以配對的字元以 . 表示，則對於 $s =$ ][]][]][][[[ 可以得到以下結果 ]..]..]..[[[ ，將可以配對的部分省略後，可以得到 ]]][[[ 的形式。

不難發現，所有無法配對的閉括號 ']' ，一定會出現在所有無法配對的開括號 '[' 的左邊。而在交換時需要先處理最左邊的無法配對的閉括號 ']' ，可以貪心地將其與最右邊的無法配對的開括號 '[' 進行交換，依此類推。而每次交換看似只能處理一對括號，但其實可以同時處理兩個括號，例如：

交換 ][ 中的最左邊的 ] 和最右邊的 [ ，可以得到 .. ，交換次數為 $1$ 。
交換 ]][[ 中的最左邊的 ] 和最右邊的 [ ，可以得到 [][] $=$ .... ，交換次數為 $1$ 。
交換 ]]][[[ 中的最左邊的 ] 和最右邊的 [ ，可以得到 ..][.. ，交換次數為 $1$ 。接著處理 ][ ，總交換次數為 $2$ 。
交換 ]]]][[[[ 中的最左邊的 ] 和最右邊的 [ ，可以得到 ..]][[.. ；接著處理 ]][[ ，總交換次數為 $2$ 。

故可以依照無法配對的對數 $cnt$ ，計算出最少需要交換的次數為 $\lceil \frac{cnt}{2} \rceil$ 。

此外，由於堆疊中只會出現 '[' ，因此可以只使用一個計數器 $cnt$ 來維護無法配對的括號對數，而不需要使用堆疊。可以參考 C++ 的實現。

複雜度分析

時間複雜度： $\mathcal{O}(n)$ ，其中 $n$ 是字串的長度。每個字元只需處理一次。
空間複雜度： $\mathcal{O}(n)$ 或 $\mathcal{O}(1)$ ，最壞情況下堆疊可能存儲所有的開括號。

class Solution:
    def minSwaps(self, s: str) -> int:
        st = []
        for ch in s:
            if ch == '[':
                st.append(ch)
            elif st:
                st.pop()
        return (len(st) + 1) // 2

class Solution {
public:
    int minSwaps(string s) {
        int cnt = 0;
        for (char ch : s) {
            if (ch == '[') {
                cnt++;
            } else if (cnt) {
                cnt--;
            }
        }
        return (cnt + 1) / 2;
    }
};