From f1299c65b0a2d50a27cea1977fb85628684789f7 Mon Sep 17 00:00:00 2001 From: Jack Sangdahl Date: Sat, 24 May 2025 20:10:17 -0600 Subject: 2131. longest palindroe by concatenating two letter words --- longest_palindrome_concat_two_word.c | 36 +++++++++++++++++++++++++++ longest_palindrome_concat_two_word.py | 46 +++++++++++++++++++++++++++++++++++ 2 files changed, 82 insertions(+) create mode 100644 longest_palindrome_concat_two_word.c create mode 100644 longest_palindrome_concat_two_word.py diff --git a/longest_palindrome_concat_two_word.c b/longest_palindrome_concat_two_word.c new file mode 100644 index 0000000..f1b4533 --- /dev/null +++ b/longest_palindrome_concat_two_word.c @@ -0,0 +1,36 @@ +// 2131. Longest Palindrome by Concatenating Two Letter Words +#include "leetcode.h" + +/* + * 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. + */ + +int longestPalindrome(char **words, int wordsSize) { + int freq[26][26] = {0}, ans = 0; + for (int i = 0; i < wordsSize; i++) { + if (freq[words[i][1] - 'a'][words[i][0] - 'a']) { + freq[words[i][1] - 'a'][words[i][0] - 'a']--; + ans += 4; + } else + freq[words[i][0] - 'a'][words[i][1] - 'a']++; + } + for (int i = 0; i < 26; i++) + if (freq[i][i]) { + ans += 2; + break; + } + return ans; +} + +int main() { + char *w1[] = {"lc", "cl", "gg"}, *w2[] = {"ab", "ty", "yt", "lc", "cl", "ab"}, + *w3[] = {"cc", "ll", "xx"}; + printf("%d\n", longestPalindrome((char **)w1, ARRAY_SIZE(w1))); // expect: 6 + printf("%d\n", longestPalindrome((char **)w2, ARRAY_SIZE(w2))); // expect: 8 + printf("%d\n", longestPalindrome((char **)w3, ARRAY_SIZE(w3))); // expect: 2 +} 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"])) -- cgit v1.2.3