<p>You are given an array of strings <code>words</code>. Each element of <code>words</code> consists of <strong>two</strong> lowercase English letters.</p>

<p>Create the <strong>longest possible palindrome</strong> by selecting some elements from <code>words</code> and concatenating them in <strong>any order</strong>. Each element can be selected <strong>at most once</strong>.</p>

<p>Return <em>the <strong>length</strong> of the longest palindrome that you can create</em>. If it is impossible to create any palindrome, return <code>0</code>.</p>

<p>A <strong>palindrome</strong> is a string that reads the same forward and backward.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> words = [&quot;lc&quot;,&quot;cl&quot;,&quot;gg&quot;]
<strong>Output:</strong> 6
<strong>Explanation:</strong> One longest palindrome is &quot;lc&quot; + &quot;gg&quot; + &quot;cl&quot; = &quot;lcggcl&quot;, of length 6.
Note that &quot;clgglc&quot; is another longest palindrome that can be created.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> words = [&quot;ab&quot;,&quot;ty&quot;,&quot;yt&quot;,&quot;lc&quot;,&quot;cl&quot;,&quot;ab&quot;]
<strong>Output:</strong> 8
<strong>Explanation:</strong> One longest palindrome is &quot;ty&quot; + &quot;lc&quot; + &quot;cl&quot; + &quot;yt&quot; = &quot;tylcclyt&quot;, of length 8.
Note that &quot;lcyttycl&quot; is another longest palindrome that can be created.
</pre>

<p><strong class="example">Example 3:</strong></p>

<pre>
<strong>Input:</strong> words = [&quot;cc&quot;,&quot;ll&quot;,&quot;xx&quot;]
<strong>Output:</strong> 2
<strong>Explanation:</strong> One longest palindrome is &quot;cc&quot;, of length 2.
Note that &quot;ll&quot; is another longest palindrome that can be created, and so is &quot;xx&quot;.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= words.length &lt;= 10<sup>5</sup></code></li>
	<li><code>words[i].length == 2</code></li>
	<li><code>words[i]</code> consists of lowercase English letters.</li>
</ul>

class item {
public:
    string word;
    int freq;

    item(string a, int b) : word(a), freq(b) {};
    const bool operator<(item a) const {
        return a.freq > this->freq;
    }
};

class Solution {
public:
    int longestPalindrome(vector<string>& words) {
        vector<vector<string>> word_dict(26, vector<string>());

        unordered_map<string, int> umap1;
        priority_queue<item> umap2;

        for (int i = 0; i < words.size(); i++) {
            umap1[words[i]]++;
        }

        int ret = 0;

        while (!umap1.empty()) {
            auto it = umap1.begin();

            string reverse_word = it->first;
            reverse(reverse_word.begin(), reverse_word.end());

            if (it->first.compare(reverse_word) == 0) {
                umap2.emplace(it->first, it->second);
                umap1.erase(it->first);
                continue;
            }
            else {
                if (umap1.count(reverse_word)) {
                    ret += min(it->second, umap1[reverse_word]) * 2;
                    umap1.erase(it->first);
                    umap1.erase(reverse_word);
                }
                else {
                    umap1.erase(it->first);
                }
            }
        }

        ret *= 2;

        int odd_added = 0;

        while (!umap2.empty()) {
            if (odd_added == 0) {
                if (umap2.top().freq % 2 == 1) {
                    odd_added = 1;
                    ret += umap2.top().freq * 2;
                }
                else {
                    ret += umap2.top().freq * 2;
                }
            }
            else {
                ret += (umap2.top().freq - umap2.top().freq % 2) * 2;
            }


            umap2.pop();
        }

        return ret;
    }
};
173400