<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: List[str]) -> int:
        max_length = 0
        visited = set()  # 이미 처리한 단어를 저장하는 집합
        word_count = Counter(words)  # 각 단어의 빈도를 카운트

        for w in words:
            rw = w[::-1]  # reversed(w)를 문자열로 변환
            if rw in word_count and word_count[rw] > 0 and word_count[w] > 0:
                if w == rw:  # 만약 단어가 "aa"처럼 자기 자신인 경우
                    pairs = word_count[w] // 2  # 짝수 개수만큼 사용 가능
                    max_length += pairs * 4  # 한 쌍은 4만큼 길이를 증가
                    word_count[w] -= pairs * 2  # 사용한 단어 갯수 차감
                else:
                    matched_pairs = min(word_count[w], word_count[rw])  # 최소 쌍을 찾음
                    max_length += matched_pairs * 4  # 두 단어로 이루어진 쌍을 추가
                    word_count[w] -= matched_pairs  # 사용한 단어 갯수 차감
                    word_count[rw] -= matched_pairs

        # "aa", "bb" 같은 단어 중 하나가 남으면 중앙에 배치할 수 있음
        for w in word_count:
            if w[0] == w[1] and word_count[w] > 0:
                max_length += 2
                break  # 중앙에 하나만 배치 가능하므로 한 번만 추가

        return max_length

1201