[LeetCode] 2131. Longest Palindrome by Concatenating Two Letter Words (Python)

LeetCode 1706. Longest Palindrome by Concatenating Two Letter Words
🗓️ Daily LeetCoding Challenge November, Day 3
String

https://leetcode.com/problems/longest-palindrome-by-concatenating-two-letter-words/

Longest Palindrome by Concatenating Two Letter Words - LeetCode

1. 문제 설명

여러 문자열이 들어있는 리스트 words에서 원소들을 적당히 연결시켜가장 긴 팰린드롬의 길이를 리턴하는 문제이다.

이때, words에 들어있는 문자열은 반드시 소문자 두 개로 구성되고, 중복된 문자열이 있을 수도 있다.

따라서 문자열의 길이가 짝수인 팰린드롬만 고려하면 된다.

 

팰린드롬은 앞에서 뒤로 읽을 때와 뒤에서 앞으로 읽을 때 동일하게 읽히는 문자열을 의미한다.

 

아래와 같이 words가 주어진다고 가정하자.

words = ["ab", "ty", "yt", "lc", "cl", "ab"]

"ty" + "lc" + "cl" + "yt" = "tylcclyt"이므로 길이가 8인 팰린드롬을 만들 수 있다.

이것 외에도 "ty"와 "yt"의 순서를 바꾸거나 "lc" + "cl"의 순서를 바꿔서 팰린드롬을 만들 수 있으나, 길이는 8로 동일하다.

 

따라서 8을 리턴하면 된다.

---

2. 문제 접근

Naive Approach

words에 속해 있는 문자열의 길이는 반드시 2이므로 "ab", "ba"처럼 앞뒤로 같은 문자열을 찾거나,

"aa", "bb"처럼 앞뒤가 동일한 문자열을 찾아야 한다.

앞뒤가 동일한 문자열이더라도 이 문자열이 중복될 수 있으므로 짝수일 때와 홀수일 때를 나눠서 생각해야 한다.

(홀수면 문자열의 가장 가운데에 와도 팰린드롬을 만족하고, 짝수면 양 옆에 배치해야 팰린드롬을 만족하니까!)

 

위를 정리하면 총 3가지로 분류 할 수 있다.

1. 앞뒤로 같은 문자열 ("ab"와 "ba") : 두 문자열의 개수 중 작은 것의 개수를 선택하여 앞뒤로 배치한다.

2. 앞뒤가 동일한 문자열이 짝수 개 ("aa" * 2n) : 문자열의 앞뒤로 배치한다.

3. 앞뒤가 동일란 문자열이 홀수 개 ("bb" * 2n) : 문자열의 가운데로 배치한다. (단, 한 번만 가능)

 

words의 길이가 100,000까지 들어올 수 있으므로 nested loop로 구현하면 런타임이 심각하게 느릴 것이다.

따라서 words에 속한 문자열의 길이가 반드시 2인점을 이용하여 2차원 리스트에 words의 문자열을 표시하고,

2차원 리스트를 nested loop로 돌면서 팰린드롬의 길이를 계산했다.

이러한 방식으로 구현하면 처음 words를 2차원 리스트에 넣는 과정에서 linear time이 걸리고,

이를 nested loop로 돌면 O(26*26) (=constant time)이 소모되므로 최종적으로 O(n)으로 계산할 수 있다.

---

3. 참고 사항

① 하나의 문자열에서 팰린드롬의 Subsequence를 구하는 문제가 아니다. 또한 문자열이 중복될 수 있다.

이 문제는 문자열을 적절하게 선택하고 연결하여 String을 만들고, String의 길이를 구하는 문제이다.

또한 두 번 사용하라는 것이 아니지, words 안에 중복된 문자열이 존재할 수 있다. (비트로 풀다가 말아먹은 이유)

따라서 문자열을 선택할 때 중복된 문자열이 있다면 이를 고려하여 최대 길이를 구해야 한다.

 

② 문자열을 결합하여 길이를 구할 필요는 없다.

예제는 문자열을 결합하여 길이를 구했지만, 문제 이해를 위해 그러한 방식을 사용한 것이다.

팰린드롬으로 사용할 수 있는 문자열을 고르기만 하고, 길이를 더하는 과정을 반복하면 된다.

 

③ 앞뒤가 같은 문자열의 개수가 홀수인 것이 존재하는지 확인해야 한다.

앞뒤가 같은 문자열의 개수가 짝수라면 문자열의 앞뒤로 짝수 개를 모두 붙여야 한다.

만약, 앞뒤가 같은 문자열의 개수가 홀수로 존재하는 문자열이 있다면,

짝수 개를 앞뒤로 붙이고 한 번에 한하여 남은 한 개를 팰린드롬의 가운데에 넣을 수 있다.

---

4. 구현 코드

class Solution:
    def longestPalindrome(self, words: List[str]) -> int:
            board = [[0] * 26 for _ in range(26)]  # words의 문자열을 저장할 2차원 리스트
            res = 0
            odd = False
            for s, t in words:
                board[ord(s) - 97][ord(t) - 97] += 1
                
            for i in range(0, 26):
                if board[i][i] % 2 == 1:
                    odd = True
                res += (board[i][i] // 2) * 4  # 팰린드롬의 앞뒤로 삽입
                for j in range(0, i):
                    res += min(board[i][j], board[j][i]) * 4  # 팰린드롬의 앞뒤로 삽입
                    
            if odd:  # 팰린드롬의 가운데에 삽입
                res += 2
                
            return res