409. Longest Palindrome (Easy)

1.問題

• 給予一個由大小寫字母組成的string, 找出可以組成的最長迴文字串

2.想法

• 統計每個字母出現的次數

  • 出現一次者

  • 出現兩次者

• 將字元轉為int來統計

vector<int> sv(59, 0);
for(int i = 0 ; i < (int)s.size(); i++){
        sv[(int)(s[i] - 'A')]++;
}

3.程式碼

class Solution {
public:
    int longestPalindrome(string s) {
        vector<int> sv(59, 0);
        for(int i = 0 ; i < (int)s.size(); i++){
            sv[(int)(s[i] - 'A')]++;
        }
        int pairCount = 0;
        int singleCount = 0;
        for(int i = 0 ; i < 59; i++){
            while(sv[i] != 0 && sv[i] != 1 ){
                sv[i] = sv[i] - 2;
                pairCount += 2;
            }
            if(sv[i] == 1){
                singleCount++;
            }
        }
        return singleCount > 0 ? pairCount + 1 : pairCount;
    }
};

4.Performance