aboutsummaryrefslogtreecommitdiff
path: root/longest_palindrome_concat_two_word.c
blob: f1b4533f44d51714ceab2fe62a8fc84f98da6aed (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
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
}