Today’s problem

2131. Longest Palindrome by Concatenating Two Letter Words

Intuition

There are in total two ways to form a palindrome.

1. a string that has an inverse string in the list
2. a string that is a palindrome itself. In this case, the string that is palindrome can only exisit in the middle of the palindrome.

Approach

Therefore, we can use a hash to solve this problem. Note that we will first run test 1 before test 2. If there is an inverse string in the list, then put that string and the current string into the list.

Then test whether this string is a palindrome itself.

Complexity

• Time complexity:

$O(N)$, N is the length of words.

• Space complexity:

$O(N)$, N is the length of words.

Code

class Solution:
    def longestPalindrome(self, words: List[str]) -> int:
        cnt = Counter(words)
        ans = 0
        sp = 0
        for word, t in cnt.items():
            # print(word, t)
            if word[0] == word[1]:
                ans += (t - t % 2)
                sp |= (t % 2)
            else:
                ans += min(t, cnt[word[::-1]])

        return (ans + sp) * 2

Advertisement

For more solutions, please visit My blog