Leetcode 1415. 長度為 n 的所有快樂字串中字典序第 k 小的字串

這是 Leetcode 2025 年 2 月 19 日的每日一題。

題目描述
#

給定兩個整數 n 和 k，考慮所有長度為 n 的快樂字串，並按字典序排序。請回傳排序後的第 k 個字串；若快樂字串數量少於 k，則回傳空字串。

快樂字串的定義如下：

僅包含字母集合 ['a', 'b', 'c'] 中的字元
任意相鄰字元不得相同，即 s[i] != s[i+1]

解題思路 - 回溯法
#

解題直覺
#

我們可以利用回溯法產生所有快樂字串，然後選出第 k 個。

Code
#

class Solution {
public:
    // 使用 DFS 找出所有快樂字串
    void dfs(int n, string current, vector<string>& result){
        // 若目前字串長度等於 n，加入結果
        if(current.length() == n){
            result.push_back(current);
            return;
        }
        for(char i = 'a'; i <= 'c'; i++){
            // 確保相鄰字元不同
            if (!current.empty() && i == current.back()) continue;
            dfs(n, current + i, result);
        }
        return;
    }
    string getHappyString(int n, int k) {
        vector<string> result;
        string current = "";
        dfs(n, current, result);
        return (result.size() >= k) ? result[k-1] : "";
    }
};

時間複雜度：$O(2^n)$

因為長度為 $n$ 的快樂字串總數為 $3 \times 2^{(n-1)}$，所以遞迴呼叫的總次數為 $O(3 \times 2^{(n-1)}) = O(2^n)$。
空間複雜度：$O(2^n)$

使用 vector 儲存所有長度為 $n$ 的快樂字串會佔用 $O(2^n)$ 空間，此外遞迴深度最深為 $n$，總體為 $O(n + 2^n) = O(2^n)$。

解題思路 - 組合數學法
#

解題直覺
#

與其產生所有快樂字串，我們可以直接利用數學規律計算第 k 個快樂字串：

分組結構
- 將所有快樂字串依照第一個字元分成三組：以 a 開頭、b 開頭、c 開頭。
- 第一個字元確定後，每個接下來的字元有兩種選擇，因此總共為 $3 \times 2^{n-1}$ 個快樂字串。
- 使用 0-based index，可得以下分佈：
  - 第 $0$ 到 $2^{n-1}-1$ 個字串以 a 開頭。
  - 第 $2^{n-1}$ 到 $2\times 2^{n-1}-1$ 以 b 開頭。
  - 第 $2\times 2^{n-1}$ 到 $3\times 2^{n-1}-1$ 以 c 開頭。
找出第一個字元
- 使用除法 $(k−1) \div 2^{n−1}$ 得到商 $q$，可確定字串屬於哪一組：
  - $q=0 \Rightarrow$ 第一個字元為 'a'
  - $q=1 \Rightarrow$ 第一個字元為 'b'
  - $q=2 \Rightarrow$ 第一個字元為 'c'
後續字元的二進位表示
- 餘數 $r$ 決定該字串在該組內的位置。
- 由於每個字元都有兩種選擇，我們可用 $r$ 的二進位表示法來生成字串：
  - 將 $r$ 轉為長度為 $n - 1$ 的二進位字串。
  - 每一位對應一個選擇（較小或較大的字母）。

關鍵特性：保序映射
#

這種二進位編碼方式會在字典序上保持順序，並確保每個 $r$ 唯一對應一個快樂字串。

建構字串的關鍵語句如下：

result[index] = (bits[i]) ? options[prev][1] : options[prev][0];

若 bits[i] == 0，選擇字典序較小的選項 options[prev][0]
若 bits[i] == 1，選擇字典序較大的選項 options[prev][1]

每一位 bit 都能唯一對應下一個字元的選擇，因此能維持字典序的正確性。

Code
#

class Solution {
public:
    string getHappyString(int n, int k) {
        // 總快樂字串數量為 3 * 2^(n-1)
        int total = 3 * (1 << (n - 1));

        // 若 k 超出範圍，回傳空字串
        if (k > total) return "";

        // 商 q 決定開頭字元，餘數 r 決定組內位置
        auto [q, r] = div(k - 1, 1 << (n - 1));

        // 初始化結果字串
        string result(n, ' ');

        // 設定第一個字元：0 -> 'a', 1 -> 'b', 2 -> 'c'
        result[0] = 'a' + q;

        // 根據前一字元決定後續可選字元
        {% raw %}array<array<char, 2>, 3> options = {{
            {'b', 'c'}, // 若前一字元為 'a'
            {'a', 'c'}, // 若前一字元為 'b'
            {'a', 'b'}  // 若前一字元為 'c'
        }};{% endraw %}

        // 將 r 轉成二進位表示，用來決定每一步的選擇
        bitset<10> bits(r);

        // 從 i = n - 2 開始處理共 n-1 位
        for (int i = n - 2, index = 1; i >= 0; i--, index++) {
            int prev = result[index - 1] - 'a';
            result[index] = (bits[i]) ? options[prev][1] : options[prev][0];
        }

        return result;
    }
};

時間複雜度：$O(n)$

空間複雜度：$O(1)$（不含輸出字串）

方法比較
#

方法	時間複雜度	空間複雜度	優點	缺點
回溯法	$O(2^n)$	$O(2^n)$	簡單直觀，易於實作	當 $n$ 較大時效率差
組合數學法	$O(n)$	$O(1)$	高效，能直接算出結果	不如回溯法直觀