字串壓縮演算法：從暴力遞歸到數學規律的最優解

問題背景與規則定義

給定一個僅由 a、b、c 三種小寫字母組成的字串，長度不超過 200。當出現連續兩個不同字母時，可用第三個字母替換這對字母：

• ab 或 ba → c
• ac 或 ca → b
• bc 或 cb → a

目標是透過反覆替換，使最終字串長度最短，輸出該最短長度。

範例解析

• 輸入 cab：ca→b 得 bb（長度 2）；或 ab→c 得 cc（長度 2）。輸出 2。
• 輸入 bcab：路徑 1：bc→a 得 aab → ac→b 得 b（長度 1）；路徑 2：ca→b 得 bbb（長度 3）。取最短，輸出 1。

核心觀察：不變量與同餘類

定義三字母計數為 cnt_a、cnt_b、cnt_c。每次操作將兩個不同字母減 1，第三字母加 1，故總長度每次減 1，且三計數的奇偶性向量 (cnt_a%2, cnt_b%2, cnt_c%2) 在模 2 意義下不變（因為 -1 ≡ +1 (mod 2)）。

進一步，考慮 (cnt_a - cnt_b) % 3、(cnt_b - cnt_c) % 3、(cnt_c - cnt_a) % 3，這三個差值模 3 也是不變量。因此，整個過程被限制在同一個同餘類內。

最短長度的數學判定

設總長度 n = cnt_a + cnt_b + cnt_c。經過 k 次操作後長度為 n - k。最終字串只能是以下三種形式之一：

1. 全同字母：如 aaa...，長度 L，計數向量為 (L,0,0) 或排列。
2. 兩字母交替：如 abab...，但此時無法再縮減，長度 ≥ 2。
3. 單字母：長度 1。

根據不變量，可直接判定最短長度：

• 若三計數全奇或全偶（即 cnt_a%2 == cnt_b%2 == cnt_c%2），最短長度為 2。
• 否則最短長度為 1。

特例：若初始字串已無相異相鄰字母（如 aaa、bbb、ccc），則無法操作，最短長度即原長度 n。

演算法實現（O(n)）

int minLength(string s) {
    int cnt[3] = {0};
    for (char ch : s) cnt[ch - 'a']++;
    // 若只有一種字母，無法縮減
    int types = (cnt[0]>0) + (cnt[1]>0) + (cnt[2]>0);
    if (types == 1) return s.length();
    // 判斷三計數奇偶性是否一致
    if ((cnt[0]%2 == cnt[1]%2) && (cnt[1]%2 == cnt[2]%2))
        return 2;
    else
        return 1;
}

為什麼遞歸/回溯會超時？

原始碼中的遞歸函數 min_len 嘗試枚舉所有可能的替換順序，狀態數呈指數級增長。對於長度 200 的字串，搜尋空間極大，且大量重複子問題。利用不變量直接推導結果，將複雜度從指數級降為線性，是典型的「數學建模優化暴力搜尋」案例。

總結

字串壓縮問題的核心在於發現奇偶性不變量。只要統計三字母出現次數，即可 O(1) 給出答案。這類問題啟示我們：面對操作規則固定、目標為極值的問題，優先尋找守恆量或同餘不變量，往往能繞過複雜的狀態空間搜尋。