diff options
Diffstat (limited to 'longest_palindrome_concat_two_word.py')
-rw-r--r-- | longest_palindrome_concat_two_word.py | 46 |
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"])) |