LeetCode 443: String Compression

剛看到這題時，我的第一個想法是新開一個 list 把壓縮結果存起來，最後再回傳長度。

然後就看到題目要求 In-place，只能用 $O(1)$ 的空間複雜度，只好換方向想。

題目

題目連結：LeetCode 443. String Compression

給定一個字元陣列 chars，將它 原地 壓縮。壓縮規則是當連續出現的相同字元時，記錄為「字元 + 出現次數」；若只出現一次，只保留字元本身。

Example:

• Input: chars = ["a","a","b","b","c","c","c"]
• Output: 6（陣列變為 ["a","2","b","2","c","3"]）

回傳壓縮後陣列的長度，且要求只能使用 $O(1)$ 的額外空間。

In-place Overwrite 的想法

既然不能開新空間，就需要兩個指標同時在原陣列上工作：

• read：負責向前掃描，找出一段連續相同的字元，並計算出現次數 count。
• write：負責在陣列左側覆寫壓縮結果，且不會超過 read，所以不會覆蓋到還沒讀的資料。

每處理完一段連續字元，就把 c 和 count 依序寫入 chars[write]。 如果 count 為兩位數以上，則需要把 count 拆成一個一個的數字寫入。

走一遍範例

用 chars = ["a","a","b","b","c","c","c"] 跑一遍：

Table: 實際走訪過程

最後 write = 6，回傳 6。

兩位數以上 count 的處理

當出現次數達到兩位數（如 12），不能直接寫 '12' 進去一個格子，要拆成 '1' 和 '2' 分別寫入。

所以對 str(count) 裡的每個 digit 逐一寫入：

for digit in str(count):
    chars[write] = digit
    write += 1

第一次 Test 的時候就錯了，大家寫的時候要注意。

程式碼

from typing import List

def compress(chars: List[str]) -> int:
    write = 0  # 寫入的位置
    read = 0   # 目前讀到的位置

    while read < len(chars):
        c = chars[read]
        count = 0

        # 計算連續出現次數
        while read < len(chars) and chars[read] == c:
            read += 1
            count += 1

        # 寫入字元
        chars[write] = c
        write += 1

        # 如果出現次數大於 1，逐一寫入數字
        if count > 1:
            for digit in str(count):
                chars[write] = digit
                write += 1

    return write

雖然有兩層 while，但 read 從頭到尾只往前走，不會重複讀取，所以只須掃過一遍陣列。

複雜度

• 時間複雜度：$O(n)$。read 指標每個字元只走訪一次。
• 空間複雜度：$O(1)$。只用了 read、write、count、c 等常數個變數。

小結

這題因為 write 永遠不會追上 read，且壓縮後的長度一定 ≤ 原長度，所以覆寫操作不會把還沒讀的資料蓋掉。

類似的 Two Pointers 原地覆寫技巧在 27. Remove Element 和 26. Remove Duplicates from Sorted Array 也可以看到，可以一起練習感受一下。