aboutsummaryrefslogtreecommitdiff
path: root/longest_palindrome_concat_two_word.py
diff options
context:
space:
mode:
Diffstat (limited to 'longest_palindrome_concat_two_word.py')
-rw-r--r--longest_palindrome_concat_two_word.py46
1 files changed, 46 insertions, 0 deletions
diff --git a/longest_palindrome_concat_two_word.py b/longest_palindrome_concat_two_word.py
new file mode 100644
index 0000000..5c66903
--- /dev/null
+++ b/longest_palindrome_concat_two_word.py
@@ -0,0 +1,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"]))