Skip to content

2131. Longest Palindrome by Concatenating Two Letter Words 👍

  • Time: $O(n)$
  • Space: $O(26^2) = O(1)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
 public:
  int longestPalindrome(vector<string>& words) {
    int ans = 0;
    vector<vector<int>> count(26, vector<int>(26));

    for (const string& word : words) {
      const int i = word[0] - 'a';
      const int j = word[1] - 'a';
      if (count[j][i]) {
        ans += 4;
        --count[j][i];
      } else {
        ++count[i][j];
      }
    }

    for (int i = 0; i < 26; ++i)
      if (count[i][i])
        return ans + 2;

    return ans;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
  public int longestPalindrome(String[] words) {
    int ans = 0;
    int[][] count = new int[26][26];

    for (final String word : words) {
      final int i = word.charAt(0) - 'a';
      final int j = word.charAt(1) - 'a';
      if (count[j][i] > 0) {
        ans += 4;
        --count[j][i];
      } else {
        ++count[i][j];
      }
    }

    for (int i = 0; i < 26; ++i)
      if (count[i][i] > 0)
        return ans + 2;

    return ans;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
class Solution:
  def longestPalindrome(self, words: list[str]) -> int:
    ans = 0
    count = [[0] * 26 for _ in range(26)]

    for a, b in words:
      i = string.ascii_lowercase.index(a)
      j = string.ascii_lowercase.index(b)
      if count[j][i]:
        ans += 4
        count[j][i] -= 1
      else:
        count[i][j] += 1

    for i in range(26):
      if count[i][i]:
        return ans + 2

    return ans