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

解题思路

本题的核心在于回文串只需确定左半部分，右半部分由左半部分对称得到。因此问题转化为：用 s 中一半的字符（各取一半）构造一个长度为 n/2 的字符串，使其对应的完整回文串严格大于 target。

解题分两步：

1. 可行性校验：统计 s 中字符频次，若出现奇数次的字符超过 1 个，则无法构成回文，直接返回空串。
2. 贪心构造左半部分：
· 先尝试让左半部分与 target 左半部分完全一致，然后检查构造出的完整回文串是否大于 target。若是，直接返回。
· 若不行，从右向左找到第一个可以增大的位置，填入比 target 对应位置稍大的字符，该位置之后的字符按字典序最小填充（即从小到大填入剩余字符）。

---

Java 代码实现

```java
class Solution {
public String lexPalindromicPermutation(String s, String target) {
int n = s.length();
int half = n / 2;

// 1. 统计 s 中字符频次
int[] cnt = new int[26];
for (char c : s.toCharArray()) cnt[c - 'a']++;

// 2. 检查能否构成回文：奇数频次字符不能超过 1 个
int oddChar = -1;
for (int i = 0; i < 26; i++) {
if (cnt[i] % 2 == 1) {
if (oddChar != -1) return "";
oddChar = i;
}
}

// 3. 左半部分可用字符：每个字符取一半
int[] leftCnt = new int[26];
for (int i = 0; i < 26; i++) leftCnt[i] = cnt[i] / 2;

// 4. 贪心构造左半部分
int[] left = new int[half];
int[] remain = leftCnt.clone();

// 4a. 先尝试完全匹配 target 的左半部分
boolean match = true;
for (int i = 0; i < half; i++) {
int c = target.charAt(i) - 'a';
if (remain[c] > 0) {
left[i] = c;
remain[c]--;
} else {
match = false;
break;
}
}

if (match) {
// 完全匹配成功，构造完整回文串检查是否大于 target
String candidate = buildPalindrome(left, remain, oddChar, n);
if (candidate.compareTo(target) > 0) return candidate;
}

// 4b. 从右向左找第一个可以增大的位置
for (int pos = half - 1; pos >= 0; pos--) {
// 重置剩余计数
remain = leftCnt.clone();
int[] tempLeft = new int[half];
boolean ok = true;

// 填充 pos 之前的位置，与 target 一致
for (int i = 0; i < pos; i++) {
int c = target.charAt(i) - 'a';
if (remain[c] > 0) {
tempLeft[i] = c;
remain[c]--;
} else {
ok = false;
break;
}
}
if (!ok) continue;

// 在 pos 位置填入比 target[pos] 大的最小字符
int targetChar = target.charAt(pos) - 'a';
boolean found = false;
for (int c = targetChar + 1; c < 26; c++) {
if (remain[c] > 0) {
tempLeft[pos] = c;
remain[c]--;
found = true;
break;
}
}
if (!found) continue;

// pos 之后的位置填入剩余字符的最小字典序
for (int i = pos + 1; i < half; i++) {
for (int c = 0; c < 26; c++) {
if (remain[c] > 0) {
tempLeft[i] = c;
remain[c]--;
break;
}
}
}

// 构造完整回文串并检查
String candidate = buildPalindrome(tempLeft, remain, oddChar, n);
if (candidate.compareTo(target) > 0) return candidate;
}

return "";
}

// 根据左半部分构造完整回文串
private String buildPalindrome(int[] left, int[] remain, int oddChar, int n) {
int half = n / 2;
StringBuilder sb = new StringBuilder();

// 左半部分
for (int i = 0; i < half; i++) sb.append((char)(left[i] + 'a'));

// 中间字符（仅当 n 为奇数）
if (n % 2 == 1) sb.append((char)(oddChar + 'a'));

// 右半部分 = 左半部分反转
for (int i = half - 1; i >= 0; i--) sb.append((char)(left[i] + 'a'));

return sb.toString();
}
}
```

---

复杂度分析

指标 复杂度
时间复杂度 O(n × 26) ≈ O(n)，其中 n 为字符串长度，字符集大小为 26
空间复杂度 O(n)（存储左半部分数组和结果字符串）