aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorJack Sangdahl <[email protected]>2025-05-24 20:10:17 -0600
committerJack Sangdahl <[email protected]>2025-05-24 20:10:32 -0600
commitf1299c65b0a2d50a27cea1977fb85628684789f7 (patch)
treee113310382d971932a033c8c05434b47d83e3ae0
parent3511e79e0d439127357bf34bd8d5b726a9092028 (diff)
downloadleetcode-f1299c65b0a2d50a27cea1977fb85628684789f7.tar.gz
leetcode-f1299c65b0a2d50a27cea1977fb85628684789f7.zip
2131. longest palindroe by concatenating two letter words
-rw-r--r--longest_palindrome_concat_two_word.c36
-rw-r--r--longest_palindrome_concat_two_word.py46
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"]))