LeetCode 解題筆記：3734. Lexicographically Smallest Palindromic Permutation Greater Than Target

作者：王一哲
日期：2026年8月28日


LeetCode 題目連結：3734. Lexicographically Smallest Palindromic Permutation Greater Than Target

解題想法

困難題。題目給一個原來的字串 $s$ 及目標字串 $target$，兩個字串長度皆為 $n$，要找到一個大於 $target$ 且字典序最小的迴文字串，如果沒有則回傳空字串。這題與昨天的題目 3720. Lexicographically Smallest Permutation Greater Than Target 很像，但是多了迴文的條件，難度高很多。主要分成以下 3 個步驟：

1. 先檢查 $s$ 是否能組成迴文字串
2. 準備前半段可用的字母並將相異字母排序
3. 用 DFS 遞迴及回溯找答案，但是要加上剪枝節省時間，剪枝條件有
   1. 如果 is_greater 等於 False，不能放比 $target[idx]$ 小的字母。
   2. 如果 new_is_greater 等於 True，用剩下的字母組成答案。

Python 程式碼

Runtime: 11 ms, beats 90.91%. Memory: 20.40 MB, beats 7.58%.

class Solution:
    def lexPalindromicPermutation(self, s: str, target: str) -> str:
        n = len(s)  # 長度
        cnt = Counter(s)  # 字母計數器

        # 1. 先檢查 s 是否能組成迴文字串
        odd_cnt = 0  # 有幾個字母的數量為奇數數量
        mid_char = ""  # 如果某個字母數量為奇數，只能放在中間
        for char, freq in cnt.items():
            if freq % 2 == 1:
                odd_cnt += 1
                mid_char = char
        if odd_cnt > 1:  # 不只一個字母數量是奇數，回傳空字串
            return ""

        # 2. 準備前半段可用的字母並將相異字母排序
        half_cnt = {char: freq // 2 for char, freq in cnt.items() if freq // 2 > 0}
        unique_chars = sorted(half_cnt.keys())
        ans = ""  # 答案
        m = n // 2  # 前半段長度

        # 3. 主要的解題過程
        def dfs(idx, is_greater, path):
            nonlocal ans
            if ans: return True

            # 遞迴出口，已經填滿前半段
            if idx == m:
                # 組合成整個字串 = 前半段 + 中間字母 + path 反序組成的後半段
                full = "".join(path) + mid_char + "".join(path[::-1])
                # 如果 full > target，找到答案
                if full > target:
                    ans = full
                    return True
                return False

            # 由小到大檢查可用的字母
            for char in unique_chars:
                # 跳過已經用完的字母
                if half_cnt[char] == 0: continue
                # 剪枝，如果 is_greater == False，不能放比 target[idx] 小的字母
                if not is_greater and char < target[idx]: continue
                # 更新 char 的數量、path 及狀態
                half_cnt[char] -= 1
                path.append(char)
                new_is_greater = is_greater or (char > target[idx])
                # 剪枝，如果 new_is_greater == True，用剩下的字母組成答案
                if new_is_greater:
                    # 找出剩下的字母
                    rem = []
                    for c in unique_chars:
                        rem.extend([c] * half_cnt[c])
                    # 組成完整的前半段字串
                    first = "".join(path) + "".join(rem)
                    # 組成完整的答案
                    ans = first + mid_char + first[::-1]
                    return True
                # 遞迴
                if dfs(idx + 1, new_is_greater, path): return True
                # 回溯
                path.pop()
                half_cnt[char] += 1
            # 預設回傳 False
            return False

        # 呼叫 dfs 找答案
        dfs(0, False, [])
        return ans

C++ 程式碼

Runtime: 24 ms, beats 27.69%. Memory: 18.64 MB, beats 32.31%.

class Solution {
public:
    int n, m;  // 長度，前半段的長度
    map<char, int> cnt, half_cnt;  // 字母計數器，前半段字母計數器
    vector<char> unique_chars;  // 前半段不重複的字母
    string mid_char, ans;  // 中間的字母，答案

    /* 主要的解題過程 */
    bool dfs(int idx, bool is_greater, string path, const string& target) {
        // 已經有答案，回傳 true
        if (!ans.empty()) return true;
        // 遞迴出口，已經檢查完所有的字母
        if (idx == m) {
            // 組合成完整的字串
            string last (path.crbegin(), path.crend());
            string full = path + mid_char + last;
            // 如果 full > target，找到答案
            if (full > target) {
                ans = full;
                return true;
            }
            return false;
        }
        // 由小到大檢查字母
        for(char ch : unique_chars) {
            // 跳過已經用完的字母
            if (half_cnt[ch] == 0) continue;
            // 剪枝，如果 is_greater == false，不能接小於 target[idx] 的字母
            if (!is_greater && ch < target[idx]) continue;
            // 試著將 ch 接到 path 後面
            path += ch;
            half_cnt[ch]--;
            bool new_is_greater = is_greater || (ch > target[idx]);
            // 剪枝，如果 new_is_greater == true，找到答案
            if (new_is_greater) {
                // 用剩下的字母組成答案
                string rem;
                for(char c : unique_chars) {
                    for(int i = 0; i < half_cnt[c]; i++) {
                        rem += c;
                    }
                }
                string left = path + rem;
                string right (left.crbegin(), left.crend());
                ans = left + mid_char + right;
                return true;
            }
            // 遞迴
            if (dfs(idx + 1, new_is_greater, path, target)) return true;
            // 回溯
            path.pop_back();
            half_cnt[ch]++;
        }
        return false;
    }

    string lexPalindromicPermutation(string s, string target) {
        /* 0. 前置作業 */
        n = (int)s.size();
        m = n / 2;
        for(char c : s) cnt[c]++;

        /* 1. 檢查 s 是否可以組成迴文字串並找出中間的字母 */
        int odd_cnt = 0;  // 數量為奇數的字母數量
        mid_char.clear();
        for(auto it : cnt) {
            if (it.second % 2 == 1) {
                odd_cnt++;
                mid_char += it.first;
            }
        }
        // 超過一個字母數量是奇數，不能組成迴文字串，回傳空字串
        if (odd_cnt > 1) return "";

        /* 2. 找出前半段可用的字母 */
        for(auto it : cnt) {
            if (it.second / 2 > 0) {
                half_cnt[it.first] = it.second / 2;
            }
        }
        for(auto it : half_cnt) {
            unique_chars.push_back(it.first);
        }
        sort(unique_chars.begin(), unique_chars.end());

        /* 3. DFS */
        string path;
        ans.clear();  // 先清空
        dfs(0, false, path, target);
        return ans;
    }
};