当前位置：首页 > news >正文

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

news 2026/7/27 8:30:37

解题思路

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

核心性质：回文串由左半部分 + 中间字符（若长度为奇数）+ 右半部分（左半部分的反转）组成。因此，我们只需构造左半部分，并保证最终完整回文串的字典序大于 target。

---

算法步骤

1. 可行性检查
统计 s 中每个字符的出现次数。若出现奇数次的字符数量 > 1，则无法构成回文，直接返回空字符串。
2. 构造左半部分的候选字符池
每个字符可用次数 = 出现次数 / 2（向下取整）。
记 half = n / 2，我们要从这些字符中选择 half 个排列成左半部分。
3. 贪心构造最小的大于 target 的回文串
我们首先尝试让左半部分与 target 的左半部分完全一致。
· 若成功且构造出的完整回文串 > target，则直接返回。
· 否则，需要修改左半部分的某个位置（从右向左扫描），使其变大，而该位置之前的字符保持不变（与 target 一致），之后的字符则填充剩余字符的最小字典序排列。
这样就能得到满足条件的最小回文串。
4. 返回结果
如果所有尝试都失败，则返回空字符串。

---

Rust 代码实现

```rust
impl Solution {
pub fn lex_palindromic_permutation(s: String, target: String) -> String {
let n = s.len();
let half = n / 2;

// 1. 统计 s 的字符频率
let mut cnt = [0; 26];
for ch in s.chars() {
cnt[(ch as u8 - b'a') as usize] += 1;
}

// 2. 检查能否构成回文
let mut odd_char = None;
for i in 0..26 {
if cnt[i] % 2 == 1 {
if odd_char.is_some() {
return String::new();
}
odd_char = Some(i);
}
}

// 3. 左半部分可用字符数（一半）
let mut left_cnt = [0; 26];
for i in 0..26 {
left_cnt[i] = cnt[i] / 2;
}

// 4. 尝试构造左半部分
// 4a. 先尝试完全匹配 target 的左半部分
let target_chars: Vec<usize> = target.chars()
.map(|c| (c as u8 - b'a') as usize)
.collect();
let mut left = vec![0; half];
let mut remain = left_cnt.clone();
let mut ok = true;

for i in 0..half {
let c = target_chars[i];
if remain[c] > 0 {
left[i] = c;
remain[c] -= 1;
} else {
ok = false;
break;
}
}

if ok {
let candidate = Self::build_palindrome(&left, odd_char, n);
if candidate > target {
return candidate;
}
}

// 4b. 从右向左找第一个可以增大的位置
for pos in (0..half).rev() {
// 重置剩余计数，并复制左侧可用计数
let mut remain = left_cnt.clone();
let mut temp_left = vec![0; half];
let mut possible = true;

// 填充 pos 之前的位置，与 target 保持一致
for i in 0..pos {
let c = target_chars[i];
if remain[c] > 0 {
temp_left[i] = c;
remain[c] -= 1;
} else {
possible = false;
break;
}
}
if !possible {
continue;
}

// 在 pos 位置尝试比 target[pos] 大的最小字符
let target_c = target_chars[pos];
let mut found = false;
for c in (target_c + 1)..26 {
if remain[c] > 0 {
temp_left[pos] = c;
remain[c] -= 1;
found = true;
break;
}
}
if !found {
continue;
}

// pos 之后的位置填充剩余字符的最小字典序
for i in (pos + 1)..half {
for c in 0..26 {
if remain[c] > 0 {
temp_left[i] = c;
remain[c] -= 1;
break;
}
}
}

// 构造完整回文串并检查是否大于 target
let candidate = Self::build_palindrome(&temp_left, odd_char, n);
if candidate > target {
return candidate;
}
}

String::new()
}

// 根据左半部分和中间字符构建完整回文串
fn build_palindrome(left: &[usize], odd_char: Option<usize>, n: usize) -> String {
let mut res = String::with_capacity(n);
// 左半部分
for &c in left {
res.push((c as u8 + b'a') as char);
}
// 中间字符（n 为奇数时）
if let Some(c) = odd_char {
res.push((c as u8 + b'a') as char);
}
// 右半部分 = 左半部分的反转
for &c in left.iter().rev() {
res.push((c as u8 + b'a') as char);
}
res
}
}
```