blob: 5c6690367dadc1410397e5c99915cdc50c839157 (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
|
# 2131. Longest Palindrome by Concatenating Two Letter Words
from collections import defaultdict
"""
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 select at most once. return the length of the longest
palindrome you can create. if it is impossible, return 0. a palindrome is a
string that reads the same forward and backward.
"""
class Solution(object):
def longestPalindrome(self, words):
"""
:type words: List[str]
:rtype: int
"""
map = defaultdict(int)
unpaired, ans = 0, 0
for i in words:
if i[0] == i[1]:
if map[i] > 0:
unpaired -= 1
map[i] -= 1
ans += 4
else:
map[i] += 1
unpaired += 1
else:
if map[i[::-1]] > 0:
ans += 4
map[i[::-1]] -= 1
else:
map[i] += 1
if unpaired > 0:
ans += 2
return ans
if __name__ == "__main__":
obj = Solution()
print(obj.longestPalindrome(words=["lc", "cl", "gg"]))
print(obj.longestPalindrome(words=["ab", "ty", "yt", "lc", "cl", "ab"]))
print(obj.longestPalindrome(words=["cc", "ll", "xx"]))
|