[LeetCode] 2131 | Longest Palindrome by Concatenating Two Letter Words | Python

---

문제 링크: https://leetcode.com/problems/longest-palindrome-by-concatenating-two-letter-words/

---

문제

You are given an array of strings words. Each element of words consists of two lowercase English letters.

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

Return the length of the longest palindrome that you can create. If it is impossible to create any palindrome, return 0.

A palindrome is a string that reads the same forward and backward.

---

조건

• 1 <= words.length <= $10^5$
• words[i].length == 2
• words[i] consists of lowercase English letters.

---

내 풀이

count라는 dictionary에는 word의 빈도수를 저장한다.

같은 글자로만 이루어진 단어(ex. 'aa')는 palindrome의 중심에 위치할 수 있기 때문에 한번만 등장하는, 같은 글자로 이루어진 단어의 수를 dup에 저장한다.

만약 word가 같은 글자로만 이루어져있다면(word[0]==word[1]), 그리고 같은 글자가 이미 이전에 나온적이 있다면(count[word]>0) 지금의 word와 이전의 word를 묶어 양쪽에 배치할 수 있다.

이전의 word를 사용하기 때문에 count[word]-=1을 하고, 두 글자를 각각 양쪽에 배치하면 전체 글자수는 4개 늘어나기 때문에 ans += 4를 한다.

 

만약 word가 같은 글자로 이루어지지 않았다면, word를 뒤집은 문자가 이전에 나왔을 때(count[word[::-1]]>0), 그 문자와 word를 묶어서 양쪽에 배치할 수 있기 때문에 ans+=4를 진행한다.

 

맨 마지막에 dup이 여러개 존재하더라도 중심에는 하나만 올 수 있기 때문에 dup>0이라면 ans+2를 리턴하고, 그렇지 않다면 ans를 리턴한다.

---

코드

class Solution:
    def longestPalindrome(self, words: List[str]) -> int:
        count = defaultdict(int)
        dup = 0
        ans = 0
        
        for idx, word in enumerate(words):
            if word[0] == word[1]:
                if count[word] > 0:
                    dup -= 1
                    count[word] -= 1
                    ans += 4
                else:
                    count[word] += 1
                    dup += 1
            else:
                if count[word[::-1]] > 0:
                    ans += 4
                    count[word[::-1]] -= 1
                else:
                    count[word] += 1
                
        return ans + 2 if dup > 0 else ans