給定字串
s和整數k，反覆從字串中移除由k個相同字元組成的相鄰重複子串，直到無法再移除為止。回傳最終結果。
Example:
Input: s = “deeedbbcccbdaa”, k = 3 Output: “aa”
Intuition
TIP
核心思路：用堆疊記錄 (字元, 連續次數)，當次數達到 k 時彈出，自動處理消除後的連鎖反應。
- 消除後前後可能又形成新的 k 個重複，類似消消樂
- 堆疊天然支援這種「消除後回溯」的行為
- 每個元素記錄字元和計數，避免重複掃描
Approaches
1. Brute Force — O(n^2 / k) / O(n)
- Idea: 反覆掃描字串，找到 k 個連續相同字元就刪除，直到沒有可刪除的為止
- Time:
O(n^2 / k)- 最壞情況 - Space:
O(n)
class Solution {
fun removeDuplicates(s: String, k: Int): String {
var str = StringBuilder(s)
var changed = true
while (changed) {
changed = false
var count = 1
for (i in 1 until str.length) {
if (str[i] == str[i - 1]) {
count++
if (count == k) {
str.delete(i - k + 1, i + 1)
changed = true
break
}
} else {
count = 1
}
}
}
return str.toString()
}
}⭐ 2. Stack Counting — O(n) / O(n)
- Idea: 堆疊存
Pair(字元, 計數)，新字元與棧頂相同就加一，達到 k 就移除，否則 push 新配對 - Time:
O(n)- 每個字元最多入棧出棧各一次 - Space:
O(n)
class Solution {
fun removeDuplicates(s: String, k: Int): String {
// stack 存 (字元, 連續出現次數)
val stack = ArrayDeque<Pair<Char, Int>>()
for (c in s) {
if (stack.isNotEmpty() && stack.last().first == c) {
val newCount = stack.last().second + 1
if (newCount == k) {
stack.removeLast()
} else {
stack.removeLast()
stack.addLast(c to newCount)
}
} else {
stack.addLast(c to 1)
}
}
val sb = StringBuilder()
for ((ch, count) in stack) {
repeat(count) { sb.append(ch) }
}
return sb.toString()
}
}🔑 Takeaways
- Pattern: 「消除相鄰重複」問題，堆疊搭配計數器可以一次遍歷解決
- Key trick: 堆疊中存 (字元, 計數) 配對，避免反覆掃描。消除後自動和前面的元素比較（棧頂變化），處理連鎖反應