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

解题思路

本题要求用字符串 s 中的字符重新排列成一个回文串，使得该回文串的字典序严格大于 target，且在所有可能的回文串中字典序最小。

回文串由左半部分 + 中间字符（若长度为奇数）+ 右半部分（左半部分的反转） 构成。因此，我们只需关注左半部分的构造，右半部分自动对称生成。

算法步骤

1. 可行性检查
      统计 s 中每个字符的出现次数。若出现奇数次的字符数量 > 1，则无法构成回文，直接返回空字符串。
2. 准备左半部分的字符池
      每个字符可用的数量为 count // 2，左半部分总长度为 n // 2。
3. 贪心构造左半部分
   · 尝试完全匹配 target 的左半部分：若成功且构造出的完整回文串大于 target，直接返回。
   · 否则，从右向左扫描左半部分，寻找第一个可以增大的位置 pos：
     · 保持 pos 之前的字符与 target 对应位置完全一致（利用可用字符）。
     · 在 pos 处填入比 target[pos] 大的最小字符。
     · 将 pos 之后的位置填入剩余字符的最小字典序排列（从小到大依次填充）。
   · 构造完整回文串，若大于 target 则返回；否则继续尝试更靠左的位置。
   · 若所有尝试均失败，返回空字符串。

—

Python3 代码

```python
class Solution:
    def lexPalindromicPermutation(self, s: str, target: str) -> str:
        n = len(s)
        half = n // 2

        # 1. 统计字符频率
        cnt = [0] * 26
        for ch in s:
            cnt[ord(ch) – ord('a')] += 1

        # 2. 检查能否构成回文（奇数频次的字符最多一个）
        odd_char = -1
        for i in range(26):
            if cnt[i] % 2 == 1:
                if odd_char != -1:
                    return ""
                odd_char = i

        # 3. 左半部分可用字符数量（每个字符取一半）
        left_cnt = [c // 2 for c in cnt]

        # 辅助函数：根据左半部分和中间字符构造完整回文串
        def build_palindrome(left: list, odd: int) -> str:
            res = []
            # 左半部分
            for c in left:
                res.append(chr(c + ord('a')))
            # 中间字符
            if odd != -1:
                res.append(chr(odd + ord('a')))
            # 右半部分（左半部分反转）
            for c in reversed(left):
                res.append(chr(c + ord('a')))
            return ''.join(res)

        # 4. 先尝试直接匹配 target 的左半部分
        target_left = [ord(ch) – ord('a') for ch in target[:half]]
        left = [0] * half
        remain = left_cnt[:]
        ok = True

        for i in range(half):
            c = target_left[i]
            if remain[c] > 0:
                left[i] = c
                remain[c] -= 1
            else:
                ok = False
                break

        if ok:
            candidate = build_palindrome(left, odd_char)
            if candidate > target:
                return candidate

        # 5. 从右向左尝试修改某个位置（贪心找最小的大于 target 的回文串）
        for pos in range(half – 1, -1, -1):
            remain = left_cnt[:]          # 重置可用字符计数
            temp_left = [0] * half
            possible = True

            # 填充 pos 之前的位置，与 target 完全一致
            for i in range(pos):
                c = target_left[i]
                if remain[c] > 0:
                    temp_left[i] = c
                    remain[c] -= 1
                else:
                    possible = False
                    break
            if not possible:
                continue

            # 在 pos 位置尝试填入比 target[pos] 大的最小字符
            target_c = target_left[pos]
            found = False
            for c in range(target_c + 1, 26):
                if remain[c] > 0:
                    temp_left[pos] = c
                    remain[c] -= 1
                    found = True
                    break
            if not found:
                continue

            # pos 之后的位置填入剩余字符的最小字典序（从小到大）
            for i in range(pos + 1, half):
                for c in range(26):
                    if remain[c] > 0:
                        temp_left[i] = c
                        remain[c] -= 1
                        break

            # 构造完整回文串并检查是否大于 target
            candidate = build_palindrome(temp_left, odd_char)
            if candidate > target:
                return candidate

        return ""
```

—

复杂度分析

· 时间复杂度：O(26 × n) ≈ O(n)，其中 n 为字符串长度，常数 26 是字符集大小。每次尝试填充时都要扫描 26 个字符，但整体线性。
· 空间复杂度：O(n)，用于存储左半部分数组和结果字符串。

—

示例验证

```python
# 示例
sol = Solution()
print(sol.lexPalindromicPermutation("abccba", "aaaaaa"))   # 输出: "abccba" (恰好等于 target？不，需要严格大于，若无则返回空)
print(sol.lexPalindromicPermutation("abc", "abc"))        # 输出: "" (无法构成回文)
print(sol.lexPalindromicPermutation("aabb", "aaaa"))      # 输出: "abba" (用 a,a,b,b 构成最小大于 "aaaa" 的回文)
```

代码清晰，能正确解决问题。如有疑问欢迎继续交流！