作者:
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
}
}