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 代码pythonclass Solution:def lexPalindromicPermutation(self, s: str, target: str) - str:n len(s)half n // 2# 1. 统计字符频率cnt [0] * 26for ch in s:cnt[ord(ch) - ord(a)] 1# 2. 检查能否构成回文奇数频次的字符最多一个odd_char -1for 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] * halfremain left_cnt[:]ok Truefor i in range(half):c target_left[i]if remain[c] 0:left[i] cremain[c] - 1else:ok Falsebreakif 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] * halfpossible True# 填充 pos 之前的位置与 target 完全一致for i in range(pos):c target_left[i]if remain[c] 0:temp_left[i] cremain[c] - 1else:possible Falsebreakif not possible:continue# 在 pos 位置尝试填入比 target[pos] 大的最小字符target_c target_left[pos]found Falsefor c in range(target_c 1, 26):if remain[c] 0:temp_left[pos] cremain[c] - 1found Truebreakif not found:continue# pos 之后的位置填入剩余字符的最小字典序从小到大for i in range(pos 1, half):for c in range(26):if remain[c] 0:temp_left[i] cremain[c] - 1break# 构造完整回文串并检查是否大于 targetcandidate build_palindrome(temp_left, odd_char)if candidate target:return candidatereturn ---复杂度分析· 时间复杂度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 的回文)代码清晰能正确解决问题。如有疑问欢迎继续交流