aboutsummaryrefslogtreecommitdiff
path: root/longest_palindrome_concat_two_word.c
diff options
context:
space:
mode:
Diffstat (limited to 'longest_palindrome_concat_two_word.c')
-rw-r--r--longest_palindrome_concat_two_word.c36
1 files changed, 36 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
+}