diff options
author | Jack Sangdahl <[email protected]> | 2025-05-24 20:10:17 -0600 |
---|---|---|
committer | Jack Sangdahl <[email protected]> | 2025-05-24 20:10:32 -0600 |
commit | f1299c65b0a2d50a27cea1977fb85628684789f7 (patch) | |
tree | e113310382d971932a033c8c05434b47d83e3ae0 | |
parent | 3511e79e0d439127357bf34bd8d5b726a9092028 (diff) | |
download | leetcode-f1299c65b0a2d50a27cea1977fb85628684789f7.tar.gz leetcode-f1299c65b0a2d50a27cea1977fb85628684789f7.zip |
2131. longest palindroe by concatenating two letter words
-rw-r--r-- | longest_palindrome_concat_two_word.c | 36 | ||||
-rw-r--r-- | longest_palindrome_concat_two_word.py | 46 |
2 files changed, 82 insertions, 0 deletions
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"])) |