# 2131. Longest Palindrome by Concatenating Two Letter Words
###### tags: `Leetcode` `Medium` `HashMap`
Link: https://leetcode.com/problems/longest-palindrome-by-concatenating-two-letter-words/
## 思路 $O(N)$ $O(N)$
先把每个字符串出现的次数存进map里面
然后分情况讨论
- 如果当下word和reverse不一样 那答案直接加上$2*word.length() *min(cnt.get(word), cnt.get(reverse))$
- 如果一样 答案加上$word.length()*2*(cnt.get(word)/2)$
- 如果一样 并且是奇数 说明有一个可以放中间 用singleMaxLen记录放中间的最长的的长度
## Code

class Solution:
    def longestPalindrome(self, words: List[str]) -> int:
        count = Counter(words)
        ans = 0
        foundCenter = False
        for word in count:
            if word[0]==word[1]:
                if count[word]%2==0:
                    ans += count[word]*2
                else:
                    ans += (count[word]-1)*2
                    ans += 2 if not foundCenter else 0
                    foundCenter = True
            elif word[::-1] in count:
                ans += min(count[word], count[word[::-1]])*4
                count[word] = count[word[::-1]] = 0
        return ans

class Solution {
    public int longestPalindrome(String[] words) {
        Map<String, Integer> cnt = new HashMap<>();
        for(String word: words){
            cnt.put(word, cnt.getOrDefault(word, 0)+1);
        }
        int len = 0;
        int singleMaxLen = 0;
        for(String word:cnt.keySet()){
            String reverse = (new StringBuilder(word)).reverse().toString();
            if(!word.equals(reverse)) len += word.length()*2*Math.min(cnt.get(word),cnt.getOrDefault(reverse,0));
            if(word.equals(reverse)) len += word.length()*2*(cnt.get(word)/2);
            if(word.equals(reverse) && cnt.get(word)%2==1) singleMaxLen = Math.max(singleMaxLen, word.length());
            cnt.put(word, 0);
            if(cnt.containsKey(reverse)) cnt.put(reverse, 0);
        }
        return len+singleMaxLen;
    }
}

class Solution {
public:
    int longestPalindrome(vector<string>& words) {
        map<string, int> map;
        for(auto word:words){
            map[word]++;
        }
        int ans = 0;
        int single = 0;
        for(auto pair:map){
            string rev = pair.first;
            reverse(rev.begin(), rev.end());
            if(pair.first[0]==pair.first[1]){
                ans+=pair.second/2*4;
                if(pair.second%2==1) single=2;
            }
            else ans+=min(map[pair.first], map[rev])*2;
        }
        return ans+single;
    }
};