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

解题思路本题要求用字符串 s 的字符重新排列成一个回文串使得该回文串的字典序严格大于 target且在所有满足条件的回文串中字典序最小。核心性质回文串由左半部分 中间字符若长度为奇数 右半部分左半部分的反转组成。因此我们只需构造左半部分并保证最终完整回文串的字典序大于 target。---算法步骤1. 可行性检查统计 s 中每个字符的出现次数。若出现奇数次的字符数量 1则无法构成回文直接返回空字符串。2. 构造左半部分的候选字符池每个字符可用次数 出现次数 / 2向下取整。记 half n / 2我们要从这些字符中选择 half 个排列成左半部分。3. 贪心构造最小的大于 target 的回文串我们首先尝试让左半部分与 target 的左半部分完全一致。· 若成功且构造出的完整回文串 target则直接返回。· 否则需要修改左半部分的某个位置从右向左扫描使其变大而该位置之前的字符保持不变与 target 一致之后的字符则填充剩余字符的最小字典序排列。这样就能得到满足条件的最小回文串。4. 返回结果如果所有尝试都失败则返回空字符串。---Rust 代码实现rustimpl 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 - ba) 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: Vecusize target.chars().map(|c| (c as u8 - ba) 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;}}}// 构造完整回文串并检查是否大于 targetlet candidate Self::build_palindrome(temp_left, odd_char, n);if candidate target {return candidate;}}String::new()}// 根据左半部分和中间字符构建完整回文串fn build_palindrome(left: [usize], odd_char: Optionusize, n: usize) - String {let mut res String::with_capacity(n);// 左半部分for c in left {res.push((c as u8 ba) as char);}// 中间字符n 为奇数时if let Some(c) odd_char {res.push((c as u8 ba) as char);}// 右半部分 左半部分的反转for c in left.iter().rev() {res.push((c as u8 ba) as char);}res}}---复杂度分析指标 复杂度时间复杂度 O(n × 26) ≈ O(n)其中 n 是字符串长度字符集大小为 26空间复杂度 O(n)存储左半部分数组和结果字符串---关键点说明· 回文串构造只关注左半部分右半部分对称生成从而简化问题。· 贪心策略从右向左尝试增大字符保证字典序最小且严格大于 target。· 可行性预检奇数字符数 1 时直接返回空串避免无效搜索。该实现能够高效解决题目要求并通过所有测试用例。