給定一個長度為
2n的字串s，只包含[和]，且各有n個。你可以交換任意兩個位置的字元，回傳使字串成為合法括號字串所需的最少交換次數。
Example:
Input: s = ”][]” Output: 1 （交換 index 0 和 index 3 得到 ”[[]]“）
Intuition
TIP
核心思路：消除所有已配對的括號後，剩下的一定是 ]]]...[[[ 形式。若剩餘未配對的 ] 有 k 個，則最少交換次數為 ⌈k/2⌉。
- 遍歷字串，用計數器模擬 Stack：遇到
[加 1，遇到]若有未配對的[就消掉，否則記錄多餘的] - 消除配對後，剩下的未配對
]數量為unmatched - 每次交換可以修復 2 個未配對（一個
]變成正確位置的[，對應的另一端也修好），所以答案是⌈unmatched / 2⌉
Approaches
1. Stack Simulation — O(n) / O(n)
- Idea: 用 Stack 消除配對括號，最後 Stack 中剩餘的就是未配對的括號數
- Time:
O(n)- 遍歷一次字串 - Space:
O(n)- Stack 最壞存 n 個字元
class Solution {
fun minSwaps(s: String): Int {
val stack = ArrayDeque<Char>()
for (c in s) {
if (c == '[') {
stack.addLast(c)
} else {
if (stack.isNotEmpty() && stack.last() == '[') {
stack.removeLast()
} else {
stack.addLast(c)
}
}
}
// stack 中剩餘的是交替的 ]...[ ，未配對的 ] 數量 = stack.size / 2
val unmatched = stack.size / 2
return (unmatched + 1) / 2
}
}⭐ 2. Greedy Counter (O(1) Space) — O(n) / O(1)
- Idea: 不用 Stack，只追蹤目前未配對的
]數量（close計數器）。遇到[時若有未配對]就消掉，否則不管；遇到]時若無[可配對就累加 - Time:
O(n)- 遍歷一次字串 - Space:
O(1)- 只用常數變數
class Solution {
fun minSwaps(s: String): Int {
var unmatched = 0 // 未配對的 ] 數量
var open = 0 // 可用的 [ 數量
for (c in s) {
if (c == '[') {
open++
} else {
if (open > 0) {
open--
} else {
unmatched++
}
}
}
return (unmatched + 1) / 2
}
}WARNING
為什麼 ⌈k/2⌉？消除配對後剩下 ]]]...[[[，每次交換最外層的一對 ] 和 [ 可以修復 2 個未配對。例如 ]][[ 只需 1 次交換變成 [[][]] 或 [[]]。
🔑 Takeaways
- Pattern: 括號配對問題 -> Stack 或計數器消除配對，再處理剩餘部分
- Key trick: 未配對括號的最少交換公式
⌈k/2⌉是 Greedy 結論，每次交換修復兩個未配對