解题思路

本题的核心在于回文串只需确定左半部分，右半部分由左半部分对称得到。因此问题转化为：用 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)（存储左半部分数组和结果字符串）