楼主:
yam276 ('_')
2025-05-26 18:53:122131. Longest Palindrome by Concatenating Two Letter Words
阵列每个成员是长度 2 chars, 像是 aa, ab, cd
找拿他们拼最长回文子字串的长度如 abcdeedcba 长度是 10
思路：
先建 HashMap 找频率
然后遍历他们
找正向跟反转的频率如 ab 就去找 ba
找他们较小频率的加上去
之后 *4 加进 res
记得两者都要减掉用过的频率
然后找第二轮
这次找重复的如 aa, bb, cc
频率直接 /2 *4 加进 res
最后看重复的有没有孤儿
有的话中间可以放一个 +2 进 res
Code:
use std::collections::HashMap;
impl Solution {
pub fn longest_palindrome(words: Vec<String>) -> i32 {
let mut freq = HashMap::new();
for word in words {
*freq.entry(word).or_insert(0) += 1;
}
let mut res = 0;
let mut center_used = false;
for (word, &count) in freq.clone().iter() {
let rev: String = word.chars().rev().collect();
if word < &rev && freq.contains_key(&rev) {
let pair_count = count.min(*freq.get(&rev).unwrap());
res += pair_count * 4;
*freq.get_mut(word).unwrap() -= pair_count;
*freq.get_mut(&rev).unwrap() -= pair_count;
}
}
for (word, &count) in freq.iter() {
let rev: String = word.chars().rev().collect();
if word == &rev {
res += (count / 2) * 4;
if count % 2 == 1 && !center_used {
res += 2;
center_used = true;
}
}
}
res
}
}