回文排列字典序 —— 枚举首个严格更大位置

日期: 2026-08-28

难度: 中等偏难

标签: 贪心、字典序、回文、枚举

题目链接：[3734. 大于目标字符串的最小字典序回文排列]

题目描述

给定字符串 s 和目标串 target（长度均为 n），返回字典序最小的字符串，它既是 s 的一个回文排列，又是字典序严格大于 target。不存在则返回空串。

示例：s = "baba", target = "abba" → "baab"（”abba” 等于 target 不算，下一个是 “baab”）
提示：n ≤ 300，小写字母

第一次思路

第一反应是逐位贪心：构造回文的前半部分，每一位选”刚好大于等于 target[i]”的最小可用字符。

// 第一版：逐位贪心 >=（卡住）
string temp = "";
for (int i = 0; i < n / 2; i++) {
    char tc = target[i];
    char rc = findJustGreaterEqual(tc);  // 卡在这里：贪心选 >=
    if (rc < tc) return "";
    else temp += rc;
}

问题：贪心选 >= 只保证”不小于”，不保证”严格大于”。如果每一位都恰好选到等于 target 的字符，最终构造出的回文串恰好等于 target——不满足”严格大于”。

反例：s = "baba", target = "abba"，半串可用字符 {a, b}。逐位贪心：target[0]='a' 选 a，target[1]='b' 选 b → 前半 "ab" → 完整回文 "abba" 等于 target，答案是 "baab" 而不是 "abba"。贪心在”等于”处停住了，看不到”下一个更大”。

最终方案

关键洞察：不要逐位贪心 >=，而是枚举”第一个严格大于 target 的位置 pos”：

在 pos 之前：与 target 完全相同（保持字典序尽可能小）
在 pos 处：放一个严格大于 target[pos] 的最小可用字符
在 pos 之后：用剩余最小字符填充（字典序最小）

这样构造出的字符串在 pos 处已经严格大于 target，后面随便填都不影响”大于”的性质——彻底避免”恰好等于 target”。

回文简化：回文由前半 half 决定（奇数长度还有一个中心字符 mid），完整回文 = half + mid(可选) + reverse(half)，只构造 half。

枚举 pos（0 ≤ pos ≤ halfLen）：

前 pos 个字符用 target[0..pos-1]，检查半串计数 halfCnt 是否足够支付；不够则此 pos 不可行
若 pos < halfLen：在 pos 处找最小的 c > target[pos] 且 tmp[c] > 0；找到则填入，剩余位置最小填充
若 pos == halfLen：前半与 target 完全相同，靠中心字符或后半部分使整体大于（构造后统一用 cand > target 判断）
所有可行 pos 产生的候选，取字典序最小的

可行性检查：奇数频率字符数 odd > 1 不可能构成回文；n 为偶数时 odd 必须为 0。

完整代码

// 最终版 — 枚举第一个严格大于位置，O(n²)
class Solution {
public:
    string lexPalindromicPermutation(string s, string target) {
        int n = s.size();
        int cnt[26] = {};
        for (char c : s) cnt[c - 'a']++;

        // 检查回文可行性：奇数频率字符最多 1 个；偶数长度时必须有 0 个
        int odd = 0;
        for (int i = 0; i < 26; i++) if (cnt[i] % 2) odd++;
        if (odd > 1) return "";
        if (n % 2 == 0 && odd != 0) return "";

        int halfLen = n / 2;
        vector<int> halfCnt(26, 0);
        char mid = 0;  // 唯一的奇数频率字符，作为中心（没有则为 0）
        for (int i = 0; i < 26; i++) {
            halfCnt[i] = cnt[i] / 2;
            if (cnt[i] % 2) mid = 'a' + i;
        }

        string best = "";
        // 枚举第一个严格大于 target 的位置 pos
        for (int pos = 0; pos <= halfLen; pos++) {
            vector<int> tmp = halfCnt;
            string half;
            bool ok = true;

            // pos 之前：与 target 完全相同（贪最小）
            for (int i = 0; i < pos; i++) {
                int idx = target[i] - 'a';
                if (tmp[idx] == 0) { ok = false; break; }  // 字符不够支付前缀
                tmp[idx]--;
                half += target[i];
            }
            if (!ok) continue;

            if (pos < halfLen) {
                // pos 处：放严格大于 target[pos] 的最小可用字符
                int targetIdx = target[pos] - 'a';
                int chosen = -1;
                for (int c = targetIdx + 1; c < 26; c++) {
                    if (tmp[c] > 0) { chosen = c; tmp[c]--; break; }
                }
                if (chosen == -1) continue;  // 找不到更大的字符，此 pos 不可行
                half += char('a' + chosen);

                // pos 之后：剩余最小字符填充
                for (int c = 0; c < 26; c++) {
                    while (tmp[c] > 0) {
                        half += char('a' + c);
                        tmp[c]--;
                    }
                }
            }

            // 构造完整回文：half + mid(可选) + reverse(half)
            string rev = half;
            reverse(rev.begin(), rev.end());
            string cand = half;
            if (mid > 0) cand += mid;
            cand += rev;

            // 必须严格大于 target，取字典序最小
            if (cand > target) {
                if (best == "" || cand < best) best = cand;
            }
        }
        return best;
    }
};

相比第一版的改动：不再逐位贪心 >=，改为枚举 pos（之前相等段 + 严格更大段分离）；string(1, mid) 换成更直观的 cand += mid；哈希表换成数组（遍历字符直接转下标更顺手）。

复杂度分析

复杂度	分析
时间复杂度	O(n²) — 枚举 pos（O(n)）× 每轮构造 half（O(n) + O(26)），n ≤ 300 足够
空间复杂度	O(n) — half/候选字符串

心得总结

字典序”严格大于/小于”类问题的通用解法：枚举第一个不同位置——之前相等（贪最小）、该位置严格满足（贪最小可行）、之后最小填充（贪最小）。三段分离保证”严格”且”最小”。
这道题算法技巧不深，难在构建字符串时的逻辑缜密——想到”枚举 pos”之后全是工程细节（前缀支付、找更大字符、中心处理、取最小），一步步理清即可实现。
回文问题先压缩到”前半”，完整回文由前半 + 中心（可选）决定，思考量减半。

补充：哈希表 alternative

最终版用数组 cnt[26] 统计，遍历字符时直接 cnt[c - 'a'] 转下标。用哈希表 unordered_map<char, int> 也可以——处理”找严格大于 target[pos] 的字符”时直接从 targetIdx + 1 到 'z' 枚举 char 即可，不需要转下标。两种实现等价，数组写法在”按字母序填充剩余”时更顺手。