解题思路本题的核心在于回文串只需确定左半部分右半部分由左半部分对称得到。因此问题转化为用 s 中一半的字符各取一半构造一个长度为 n/2 的字符串使其对应的完整回文串严格大于 target。解题分两步1. 可行性校验统计 s 中字符频次若出现奇数次的字符超过 1 个则无法构成回文直接返回空串。2. 贪心构造左半部分· 先尝试让左半部分与 target 左半部分完全一致然后检查构造出的完整回文串是否大于 target。若是直接返回。· 若不行从右向左找到第一个可以增大的位置填入比 target 对应位置稍大的字符该位置之后的字符按字典序最小填充即从小到大填入剩余字符。---Java 代码实现javaclass 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) {// 完全匹配成功构造完整回文串检查是否大于 targetString 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)存储左半部分数组和结果字符串
)
