# 409. Longest Palindrome (Easy)

## 1.問題

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

![](https://901207480-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LGKoChvN9am4__HCIRK%2F-LI-NssLOgnAS7u5VEFg%2F-LI-OU67NPQuY3QX_HIc%2F2018072206.jpg?alt=media\&token=c584d6ee-59b6-46dd-9a0e-f4f8225fc772)

## 2.想法&#x20;

* 統計每個字母出現的次數
  * 出現一次者
  * 出現兩次者
* 將字元轉為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

![](https://901207480-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LGKoChvN9am4__HCIRK%2F-LI-NssLOgnAS7u5VEFg%2F-LI-PUiiTD-sliiAogkw%2F2018072207.jpg?alt=media\&token=8d1cdb51-968e-4fed-a3f7-f710c566d46e)
