Re: [閒聊] 每日leetcode

[yam276 (史萊哲林的優等生)]

2131. 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
    }
}

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 114.32.48.170 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1748256794.A.AF2.html
※ 編輯: yam276 (114.32.48.170 臺灣), 05/26/2025 18:54:50
→ JIWP: 怎麼是昨天的
→ yam276: 因為我昨天想到一半
→ yam276: 我卡在Rust的鏈式結構
→ JIWP: 找一輪就好了吧
→ yam276: 我對這語言熟練度還太低了
→ JIWP: 紀錄重複字串的次數，如果有對應的就扣掉，看最後有沒有剩的
→ yam276: 靠北 AI騙我
→ yam276: 但還要跑一次找重複的有沒有剩
→ yam276: 不過O(n+k) k一定小於n就是