409. Longest Palindrome

📘 題目敘述

給定一個由小寫或大寫英文字母組成的字串 s，請回傳能用這些字母組成的最長回文字串的長度。

字母大小寫是有區分的，例如："Aa" 在這題不會被視為回文。

條件限制

• 1 <= s.length <= 2000
• s 只由小寫與/或大寫英文字母組成

🧠 解題思路

我的做法是用「配對」的概念：

• 回文的左右兩邊一定要能成對出現
• 所以我會固定一個位置 i 當作左邊的字母
• 再去 i 後面找一個相同字母的位置 j 來配成一對
• 找到就代表這個字母可以貢獻回文長度 +2
• 如果有任何字母無法配對，就代表最後回文中間可以放一個單獨字母，因此最後再 +1

所有變數

• pal：目前已經成功配對出的回文長度（每配到一對就 +2）
• left：是否存在「配不到對」的字母
• check：每一輪固定 i 時，用來判斷 s[i] 這個字母是否有成功找到配對

步驟一：特判 s 長度為 1

• 若 s.size() == 1，答案就是 1，直接回傳

步驟二：外層迴圈固定 i，內層找配對的 j

• 外層 for (int i = 0; i < s.size(); i++)：我把 s[i] 當作想配對的字母
• 內層 for (int j = i + 1; j < s.size(); j++)：從 i 後面開始找

情況一：找到配對（s[i] == s[j]）

• s.erase(j, 1)：把配對到的字母刪掉，避免重複使用
• pal = pal + 2：回文長度增加 2
• check = false 並 break：這輪結束

情況二：整輪都找不到配對（check 仍是 true）

• left = true，代表最後回文中心有機會放一個單獨字母

結束後判斷要不要補中心字母

• 如果 left == true，我做 pal = pal + 1
• 回文最多只能有一個單獨字母放在中間

💻 程式碼實作

class Solution {
public:
    int longestPalindrome(string s) {
        int len = s.size();
        bool left = false;
        int pal = 0;
        if (s.size() == 1) {
            return 1;
        }
        for (int i = 0; i < s.size(); i++) {
            bool check = true;
            for (int j = i + 1; j < s.size(); j++) {
                if (s[i] == s[j]) {
                    s.erase(j, 1);
                    pal = pal + 2;
                    check = false;
                    break;
                }
            }
            if (check) {
                left = true;
            }
        }
        if (left) {
            pal = pal + 1;
        }
        return pal;
    }
};

🔗 題目連結

https://leetcode.com/problems/longest-palindrome/