題目描述:
給定字串 s 和整數 k,反覆移除字串中 k 個連續相同字元的片段,直到無法再移除為止,回傳最終字串。
解題思路:
使用堆疊(stack),每個元素存放一對 (字元, 連續計數)。遍歷字串時,若當前字元與堆疊頂端相同,則計數加一;否則壓入新元素,計數設為 1。當頂端計數達到 k 時,彈出該元素(等同刪除 k 個連續字元)。遍歷結束後,將堆疊中的元素依序展開還原成字串即為答案。此方法只需一次遍歷,避免了反覆掃描字串的低效做法。
時間複雜度:O(n) — 每個字元最多被壓入和彈出堆疊各一次。
空間複雜度:O(n) — 堆疊最多存放 n 個元素。
1. Initialize an empty stack of (char, count) pairs
2. For each character c in s:
a. If stack is not empty and top character == c:
- Increment top count
- If top count == k, pop the top element
b. Else push (c, 1) onto stack
3. Build result string by expanding each (char, count) pair
4. Return result雙指標法 O(n):用一個慢指標寫回結果,搭配計數陣列追蹤每個位置的連續長度。當計數達到 k 時,慢指標回退 k 步。空間 O(n) 用於計數陣列,但可原地修改字串。
暴力模擬 O(n²/k):反覆掃描字串,每次找到並刪除 k 個連續字元。簡單直觀但效率差,最壞情況下需要 O(n/k) 輪掃描。