x
Q: 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 selected at most once.
Return the length of the longest palindrome that you can create. If it is impossible to create any palindrome, return 0.
A palindrome is a string that reads the same forward and backward.
A: 1. A Hash Map Approach
class Solution {243Please respect copyright.ＰＥＮＡＮＡp6jUbnD0Xj
public int longestPalindrome(String[] words) {243Please respect copyright.ＰＥＮＡＮＡMxRogW7net
HashMap<String, Integer> count = new HashMap<String, Integer>();243Please respect copyright.ＰＥＮＡＮＡnD3Ys4hqRd
// Count the number of occurrences of each word using a hashmap243Please respect copyright.ＰＥＮＡＮＡPHCx01XBSf
for (String word : words) {243Please respect copyright.ＰＥＮＡＮＡZqxfUDeVYT
Integer countOfTheWord = count.get(word);243Please respect copyright.ＰＥＮＡＮＡPGq0poMDiM
if (countOfTheWord == null) {243Please respect copyright.ＰＥＮＡＮＡKdaXZXjbJZ
count.put(word, 1);243Please respect copyright.ＰＥＮＡＮＡi0NL80hiWx
} else {243Please respect copyright.ＰＥＮＡＮＡshzEDNcIC8
count.put(word, countOfTheWord + 1);243Please respect copyright.ＰＥＮＡＮＡ9jnCghq2ZU
}243Please respect copyright.ＰＥＮＡＮＡEe7vzNWO9m
}243Please respect copyright.ＰＥＮＡＮＡa8yim32caj
// Initialize answer=0, central = false. The answer will denote the number of words in the final string and the boolean variable central will denote whether we have a central word243Please respect copyright.ＰＥＮＡＮＡTcoAeGq9Fv
int answer = 0;243Please respect copyright.ＰＥＮＡＮＡv8GeyWtBGJ
boolean central = false;243Please respect copyright.ＰＥＮＡＮＡbFcebQmI6t
for (Map.Entry<String, Integer> entry : count.entrySet()) {243Please respect copyright.ＰＥＮＡＮＡe098MdveaD
String word = entry.getKey();243Please respect copyright.ＰＥＮＡＮＡtPbDDJgAtN
int countOfTheWord = entry.getValue();243Please respect copyright.ＰＥＮＡＮＡbHgroUL13b
// if the word is a palindrome243Please respect copyright.ＰＥＮＡＮＡvWEz6RLp0C
if (word.charAt(0) == word.charAt(1)) {243Please respect copyright.ＰＥＮＡＮＡgLXrTqBWot
if (countOfTheWord % 2 == 0) {243Please respect copyright.ＰＥＮＡＮＡHA8onHWNzU
answer += countOfTheWord;243Please respect copyright.ＰＥＮＡＮＡfx6LGzWlf0
} else {243Please respect copyright.ＰＥＮＡＮＡ8BUAvabRaU
answer += countOfTheWord - 1;243Please respect copyright.ＰＥＮＡＮＡ57roTcLJ2B
central = true;243Please respect copyright.ＰＥＮＡＮＡdtGXgOVmhL
}243Please respect copyright.ＰＥＮＡＮＡ5QyWEudDRs
// consider a pair of non-palindrome words such that one is the reverse of another243Please respect copyright.ＰＥＮＡＮＡDl6ijBQnBN
} else if (word.charAt(0) < word.charAt(1)) {243Please respect copyright.ＰＥＮＡＮＡt2vNtyw5pi
String reversedWord = "" + word.charAt(1) + word.charAt(0);243Please respect copyright.ＰＥＮＡＮＡ6MJOelC4o2
if (count.containsKey(reversedWord)) {243Please respect copyright.ＰＥＮＡＮＡV9i4V2Gvib
answer += 2 * Math.min(countOfTheWord, count.get(reversedWord));243Please respect copyright.ＰＥＮＡＮＡIOyDAXdD8c
}243Please respect copyright.ＰＥＮＡＮＡzXKv0cutgS
}243Please respect copyright.ＰＥＮＡＮＡcXZFX0IUsq
}243Please respect copyright.ＰＥＮＡＮＡzReR1v95Qt
if (central) {243Please respect copyright.ＰＥＮＡＮＡ1br1I9p3Ya
answer++;243Please respect copyright.ＰＥＮＡＮＡL4Pp0r2EzC
}243Please respect copyright.ＰＥＮＡＮＡhFoKVNcSGr
return 2 * answer;243Please respect copyright.ＰＥＮＡＮＡObzzTx9pGv
}243Please respect copyright.ＰＥＮＡＮＡS8OFq0GI0k
}
2: A Two-Dimensional Array Approach
class Solution {243Please respect copyright.ＰＥＮＡＮＡRYLtIPIKPf
public int longestPalindrome(String[] words) {243Please respect copyright.ＰＥＮＡＮＡD7PCJpyBqG
final int alphabetSize = 26;243Please respect copyright.ＰＥＮＡＮＡ0A6n46KEfc
int[][] count = new int[alphabetSize][alphabetSize];243Please respect copyright.ＰＥＮＡＮＡK65w3uhbG9
// Count the number of occurrences of each word using a two-dimensional array. 243Please respect copyright.ＰＥＮＡＮＡvcvGPRn9md
for (String word : words) {243Please respect copyright.ＰＥＮＡＮＡlqmAfQohuW
count[word.charAt(0) - 'a'][word.charAt(1) - 'a']++;243Please respect copyright.ＰＥＮＡＮＡTPH3606Bix
}243Please respect copyright.ＰＥＮＡＮＡzFa7NFk0QN
// The answer will denote the number of words in the final string and the boolean variable central will denote whether we have a central word243Please respect copyright.ＰＥＮＡＮＡEmnUCvWKiT
int answer = 0;243Please respect copyright.ＰＥＮＡＮＡ0OdgPpl7pY
boolean central = false;243Please respect copyright.ＰＥＮＡＮＡfwol0xfXyl
for (int i = 0; i < alphabetSize; i++) {243Please respect copyright.ＰＥＮＡＮＡuiCnBb6YG7
if (count[i][i] % 2 == 0) {243Please respect copyright.ＰＥＮＡＮＡT3S3z3YaAQ
answer += count[i][i];243Please respect copyright.ＰＥＮＡＮＡ9iXwNfhv9Z
} else {243Please respect copyright.ＰＥＮＡＮＡFdu9yjpMjY
answer += count[i][i] - 1;243Please respect copyright.ＰＥＮＡＮＡAg6RHcS16I
central = true;243Please respect copyright.ＰＥＮＡＮＡT3KFi1kq94
}243Please respect copyright.ＰＥＮＡＮＡGvXh6gRrjv
for (int j = i + 1; j < alphabetSize; j++) {243Please respect copyright.ＰＥＮＡＮＡApSinvG8V1
answer += 2 * Math.min(count[i][j], count[j][i]);243Please respect copyright.ＰＥＮＡＮＡdeu4VHFera
}243Please respect copyright.ＰＥＮＡＮＡRLOd5tJjrJ
}243Please respect copyright.ＰＥＮＡＮＡBS4OhihQJI
if (central) {243Please respect copyright.ＰＥＮＡＮＡVLuyraWlyp
answer++;243Please respect copyright.ＰＥＮＡＮＡuE225MKeRg
}243Please respect copyright.ＰＥＮＡＮＡDkDOkeIStZ
return 2 * answer;243Please respect copyright.ＰＥＮＡＮＡt7WJj2zx7T
}243Please respect copyright.ＰＥＮＡＮＡU0GfTgYBSL
}
243Please respect copyright.ＰＥＮＡＮＡQmxLscNYYC
