1209. Remove All Adjacent Duplicates In String II

Medium

Description

給定字串 s 和整數 k，反覆從字串中移除由 k 個相同字元組成的相鄰重複子串，直到無法再移除為止。回傳最終結果。

Example:

Input: s = “deeedbbcccbdaa”, k = 3 Output: “aa”

Intuition#

核心思路：用堆疊記錄 (字元, 連續次數)，當次數達到 k 時彈出，自動處理消除後的連鎖反應。

消除後前後可能又形成新的 k 個重複，類似消消樂
堆疊天然支援這種「消除後回溯」的行為
每個元素記錄字元和計數，避免重複掃描

Approaches#

1: Brute Force#

概念: 反覆掃描字串，找到 k 個連續相同字元就刪除，直到沒有可刪除的為止
時間複雜度: O(n^2 / k) - 最壞情況
空間複雜度: 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: 堆疊計數#

概念: 堆疊存 Pair(字元, 計數)，新字元與棧頂相同就加一，達到 k 就移除，否則 push 新配對
時間複雜度: O(n) - 每個字元最多入棧出棧各一次
空間複雜度: 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: 「消除相鄰重複」問題，堆疊搭配計數器可以一次遍歷解決
關鍵技巧: 堆疊中存 (字元, 計數) 配對，避免反覆掃描。消除後自動和前面的元素比較（棧頂變化），處理連鎖反應