Hard
题目描述
给你两个长度为 n 的字符串 s 和 target，都由小写英文字母组成。
返回字典序最小的字符串，该字符串既是 s 的回文排列，又严格大于 target。如果不存在这样的排列，返回空字符串。
示例 1：
输入：s = "baba", target = "abba"
输出："baab"
解释：
s 的回文排列（按字典序）有 "abba" 和 "baab"。
严格大于 target 的字典序最小排列是 "baab"。
示例 2：
输入：s = "baba", target = "bbaa"
输出：""
解释：
s 的回文排列（按字典序）有 "abba" 和 "baab"。
它们都不严格大于 target。因此答案是 ""。
示例 3：
输入：s = "abc", target = "abb"
输出：""
解释：
s 没有回文排列。因此答案是 ""。
示例 4：
输入：s = "aac", target = "abb"
输出："aca"
解释：
s 的唯一回文排列是 "aca"。
"aca" 严格大于 target。因此答案是 "aca"。
约束：
1 <= n == s.length == target.length <= 300s和target只包含小写英文字母
解题思路
这道题需要找到字符串 s 的所有可能回文排列中，字典序最小且严格大于 target 的那一个。
解题思路：
回文排列的可能性检查：首先统计字符串 s 中每个字符的出现次数。对于回文字符串，最多只能有一个字符出现奇数次（作为中心字符）。
构造策略：回文字符串可以通过构造前半部分然后镜像得到。我们需要：
- 确定前半部分的长度：
(n + 1) / 2 - 如果字符串长度为奇数，中间位置需要特殊处理
- 贪心地选择每个位置的字符，使得结果尽可能小但要大于 target
- 确定前半部分的长度：
核心算法：
- 首先尝试构造一个与 target 前半部分相同的回文字符串
- 如果无法构造或构造出来不大于 target，则需要在某个位置增大字符
- 从右到左找到第一个可以增大的位置，增大后其右侧位置都用最小可能的字符填充
实现细节：
- 使用字符计数数组管理可用字符
- 对于每个位置，尝试使用最小的可用字符
- 构造完前半部分后镜像得到完整回文串
- 验证结果是否严格大于 target
算法的关键在于正确处理字符分配和回文约束，同时确保字典序最小且大于目标字符串。
代码实现
class Solution {
public:
string lexPalindromicPermutation(string s, string target) {
int n = s.length();
vector<int> count(26, 0);
// Count characters in s
for (char c : s) {
count[c - 'a']++;
}
// Check if palindrome is possible
int oddCount = 0;
for (int i = 0; i < 26; i++) {
if (count[i] % 2 == 1) oddCount++;
}
if (oddCount > 1) return "";
// Find middle character for odd length
char middle = 0;
if (n % 2 == 1) {
for (int i = 0; i < 26; i++) {
if (count[i] % 2 == 1) {
middle = 'a' + i;
count[i]--;
break;
}
}
}
// Half all counts for constructing first half
for (int i = 0; i < 26; i++) {
count[i] /= 2;
}
int halfLen = n / 2;
string firstHalf = "";
vector<int> used(26, 0);
// Try to construct first half
for (int pos = 0; pos < halfLen; pos++) {
char targetChar = target[pos];
bool found = false;
// Try to use same character as target
if (used[targetChar - 'a'] < count[targetChar - 'a']) {
firstHalf += targetChar;
used[targetChar - 'a']++;
found = true;
} else {
// Find next available character greater than target[pos]
for (char c = targetChar + 1; c <= 'z'; c++) {
if (used[c - 'a'] < count[c - 'a']) {
firstHalf += c;
used[c - 'a']++;
found = true;
break;
}
}
}
if (!found) {
// Backtrack and try to increment previous position
while (pos > 0) {
pos--;
char lastChar = firstHalf[pos];
used[lastChar - 'a']--;
firstHalf.pop_back();
// Try next character
bool incremented = false;
for (char c = lastChar + 1; c <= 'z'; c++) {
if (used[c - 'a'] < count[c - 'a']) {
firstHalf += c;
used[c - 'a']++;
incremented = true;
break;
}
}
if (incremented) {
pos++;
break;
}
}
if (pos == 0 && firstHalf.empty()) return "";
}
}
// Fill remaining positions with smallest available characters
while (firstHalf.length() < halfLen) {
for (int i = 0; i < 26; i++) {
if (used[i] < count[i]) {
firstHalf += ('a' + i);
used[i]++;
break;
}
}
}
// Construct full palindrome
string result = firstHalf;
if (middle != 0) result += middle;
reverse(firstHalf.begin(), firstHalf.end());
result += firstHalf;
return result > target ? result : "";
}
};
class Solution:
def lexPalindromicPermutation(self, s: str, target: str) -> str:
n = len(s)
count = [0] * 26
# Count characters in s
for c in s:
count[ord(c) - ord('a')] += 1
# Check if palindrome is possible
odd_count = sum(1 for x in count if x % 2 == 1)
if odd_count > 1:
return ""
# Find middle character for odd length
middle = ""
if n % 2 == 1:
for i in range(26):
if count[i] % 2 == 1:
middle = chr(ord('a') + i)
count[i] -= 1
break
# Half all counts for constructing first half
for i in range(26):
count[i] //= 2
half_len = n // 2
first_half = []
used = [0] * 26
# Try to construct first half
pos = 0
while pos < half_len:
target_char = target[pos]
found = False
# Try to use same character as target
if used[ord(target_char) - ord('a')] < count[ord(target_char) - ord('a')]:
first_half.append(target_char)
used[ord(target_char) - ord('a')] += 1
found = True
pos += 1
else:
# Find next available character greater than target[pos]
for c_ord in range(ord(target_char) + 1, ord('z') + 1):
c_idx = c_ord - ord('a')
if used[c_idx] < count[c_idx]:
first_half.append(chr(c_ord))
used[c_idx] += 1
found = True
pos += 1
break
if not found:
# Backtrack and try to increment previous position
while pos > 0:
pos -= 1
last_char = first_half.pop()
used[ord(last_char) - ord('a')] -= 1
# Try next character
incremented = False
for c_ord in range(ord(last_char) + 1, ord('z') + 1):
c_idx = c_ord - ord('a')
if used[c_idx] < count[c_idx]:
first_half.append(chr(c_ord))
used[c_idx] += 1
incremented = True
pos += 1
break
if incremented:
break
if pos == 0 and not first_half:
return ""
# Fill remaining positions with smallest available characters
while len(first_half) < half_len:
for i in range(26):
if used[i] < count[i]:
first_half.append(chr(ord('a') + i))
used[i] += 1
break
# Construct full palindrome
result = ''.join(first_half) + middle + ''.join(reversed(first_half))
return result if result > target else ""
public class Solution {
public string LexPalindromicPermutation(string s, string target) {
int n = s.Length;
int[] count = new int[26];
// Count characters in s
foreach (char c in s) {
count[c - 'a']++;
}
// Check if palindrome is possible
int oddCount = 0;
for (int i = 0; i < 26; i++) {
if (count[i] % 2 == 1) oddCount++;
}
if (oddCount > 1) return "";
// Find middle character for odd length
char middle = '\0';
if (n % 2 == 1) {
for (int i = 0; i < 26; i++) {
if (count[i] % 2 == 1) {
middle = (char)('a' + i);
count[i]--;
break;
}
}
}
// Half all counts for constructing first half
for (int i = 0; i < 26; i++) {
count[i] /= 2;
}
int halfLen = n / 2;
var firstHalf = new StringBuilder();
int[] used = new int[26];
// Try to construct first half
int pos = 0;
while (pos < halfLen) {
char targetChar = target[pos];
bool found = false;
// Try to use same character as target
if (used[targetChar - 'a'] < count[targetChar - 'a']) {
firstHalf.Append(targetChar);
used[targetChar - 'a']++;
found = true;
pos++;
} else {
// Find next available character greater than target[pos]
for (char c = (char)(targetChar + 1); c <= 'z'; c++) {
if (used[c - 'a'] < count[c - 'a']) {
firstHalf.Append(c);
used[c - 'a']++;
found = true;
pos++;
break;
}
}
}
if (!found) {
// Backtrack and try to increment previous position
while (pos > 0) {
pos--;
char lastChar = firstHalf[firstHalf.Length - 1];
used[lastChar - 'a']--;
firstHalf.Length--;
// Try next character
bool incremented = false;
for (char c = (char)(lastChar + 1); c <= 'z'; c++) {
if (used[c - 'a'] < count[c - 'a']) {
firstHalf.Append(c);
used[c - 'a']++;
incremented = true;
pos++;
break;
}
}
if (incremented) {
break;
}
}
if (pos == 0 && firstHalf.Length == 0) return "";
}
}
// Fill remaining positions with smallest available characters
while (firstHalf.Length < halfLen) {
for (int i = 0; i < 26; i++) {
if (used[i] < count[i]) {
firstHalf.Append((char)('a' + i));
used[i]++;
break;
}
}
}
// Construct full palindrome
string firstHalfStr = firstHalf.ToString();
var result = new StringBuilder(firstHalfStr);
if (middle != '\0') result.Append(middle);
for (int i = firstHalfStr.Length - 1; i >= 0; i--) {
result.Append(firstHalfStr[i]);
}
string finalResult = result.ToString();
return string.Compare(finalResult, target) > 0 ? finalResult : "";
}
}
var lexPalindromicPermutation = function(s, target) {
const n = s.length;
const count = new Array(26).fill(0);
for (let char of s) {
count[char.charCodeAt(0) - 97]++;
}
let oddCount = 0;
let oddChar = '';
for (let i = 0; i < 26; i++) {
if (count[i] % 2 === 1) {
oddCount++;
oddChar = String.fromCharCode(i + 97);
}
}
if (oddCount > 1) return "";
const half = Math.floor(n / 2);
const firstHalf = new Array(half).fill('');
let idx = 0;
for (let i = 0; i < 26; i++) {
const char = String.fromCharCode(i + 97);
const halfCount = Math.floor(count[i] / 2);
for (let j = 0; j < halfCount; j++) {
firstHalf[idx++] = char;
}
}
function nextPermutation(arr) {
let i = arr.length - 2;
while (i >= 0 && arr[i] >= arr[i + 1]) i--;
if (i < 0) return false;
let j = arr.length - 1;
while (arr[j] <= arr[i]) j--;
[arr[i], arr[j]] = [arr[j], arr[i]];
let left = i + 1, right = arr.length - 1;
while (left < right) {
[arr[left], arr[right]] = [arr[right], arr[left]];
left++;
right--;
}
return true;
}
function buildPalindrome(firstHalf) {
let result = firstHalf.join('');
if (oddChar) result += oddChar;
result += firstHalf.slice().reverse().join('');
return result;
}
let current = buildPalindrome(firstHalf);
if (current > target) return current;
do {
if (!nextPermutation(firstHalf)) break;
current = buildPalindrome(firstHalf);
if (current > target) return current;
} while (true);
return "";
};
复杂度分析
| 指标 | 复杂度 |
|---|---|
| 时间 | - |
| 空间 | - |