DeepSeek LeetCode 3734. 大于目标字符串的最小字典序回文排列 TypeScript实现

```typescript
function lexPalindromicPermutation(s: string, target: string): string {
const n: number = s.length;
const half: number = Math.floor(n / 2);

// 统计字符频次
const cnt: number[] = new Array(26).fill(0);
for (const ch of s) {
cnt[ch.charCodeAt(0) - 97]++;
}

// 检查能否构成回文（奇数频次字符不能超过1个）
let oddChar: number = -1;
for (let i = 0; i < 26; i++) {
if (cnt[i] & 1) {
if (oddChar !== -1) return "";
oddChar = i;
}
}

// 左半部分可用字符数量（各取一半）
const leftCnt: number[] = cnt.map(c => Math.floor(c / 2));

// 构造完整回文串
const buildPalindrome = (left: number[], odd: number): string => {
const res: string[] = [];
// 左半部分
for (const c of left) {
res.push(String.fromCharCode(c + 97));
}
// 中间字符（若有）
if (odd !== -1) {
res.push(String.fromCharCode(odd + 97));
}
// 右半部分（左半部分反转）
for (let i = left.length - 1; i >= 0; i--) {
res.push(String.fromCharCode(left[i] + 97));
}
return res.join('');
};

// target 的左半部分（数字表示）
const targetLeft: number[] = target.slice(0, half).split('').map(ch => ch.charCodeAt(0) - 97);

// 第一步：尝试完全匹配 target 的左半部分
const left: number[] = new Array(half);
const remain: number[] = leftCnt.slice();
let ok: boolean = true;
for (let i = 0; i < half; i++) {
const c = targetLeft[i];
if (remain[c] > 0) {
left[i] = c;
remain[c]--;
} else {
ok = false;
break;
}
}
if (ok) {
const candidate = buildPalindrome(left, oddChar);
if (candidate > target) return candidate;
}

// 第二步：从右向左尝试修改某个位置
for (let pos = half - 1; pos >= 0; pos--) {
const remainCopy: number[] = leftCnt.slice();
const tempLeft: number[] = new Array(half);
let possible: boolean = true;

// 保持 pos 之前与 target 一致
for (let i = 0; i < pos; i++) {
const c = targetLeft[i];
if (remainCopy[c] > 0) {
tempLeft[i] = c;
remainCopy[c]--;
} else {
possible = false;
break;
}
}
if (!possible) continue;

// 在 pos 处放入比 target[pos] 大的最小字符
const targetC = targetLeft[pos];
let found = false;
for (let c = targetC + 1; c < 26; c++) {
if (remainCopy[c] > 0) {
tempLeft[pos] = c;
remainCopy[c]--;
found = true;
break;
}
}
if (!found) continue;

// pos 之后全部填最小字典序（从小到大）
for (let i = pos + 1; i < half; i++) {
for (let c = 0; c < 26; c++) {
if (remainCopy[c] > 0) {
tempLeft[i] = c;
remainCopy[c]--;
break;
}
}
}

const candidate = buildPalindrome(tempLeft, oddChar);
if (candidate > target) return candidate;
}

return "";
}
```

核心思路：
回文串由左半部分决定，因此构造左半部分即可。先尝试与 target 左半部分完全相同，若完整回文串大于 target 则直接返回；否则从右向左寻找第一个可以增大的位置，保持前面不变，该位置填入比原字符大的最小可用字符，之后用剩余字符的最小字典序填充，最后构造回文串并返回。

复杂度：时间 O(26·n) ≈ O(n)，空间 O(n)。