<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 Solution:
    def longestPalindrome(self, words):

        counter = defaultdict(int)
        palindrome_length = 0
        central_used = False

        for word in words:
            reverse_word = word[::-1]
            if counter[reverse_word] > 0:
                palindrome_length += 4
                counter[reverse_word] -= 1
            else:
                counter[word] += 1

        for word in counter:
            if counter[word] > 0 and word[0] == word[1]:
                palindrome_length += 2
                break

        return palindrome_length


        # BRUTE FORCE
        # def is_palindrome(word1, word2):
        #     return word1[0] == word2[1] and word1[1] == word2[0]

        # n = len(words)
        # used = [False] * n
        # palindrome_length = 0

        # for i in range(n):
        #     if used[i]:
        #         continue
        #     for j in range(i + 1, n):
        #         if not used[j] and is_palindrome(words[i], words[j]):
        #             palindrome_length += 4  # Since each word is 2 letters
        #             used[i] = used[j] = True
        #             break

        # # Check for a word that can be a center of palindrome (like "gg")
        # for i in range(n):
        #     if not used[i] and words[i][0] == words[i][1]:
        #         palindrome_length += 2
        #         break

        # return palindrome_length
1109