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 {265Please respect copyright.ＰＥＮＡＮＡaNjJ9NPXfv
public int longestPalindrome(String[] words) {265Please respect copyright.ＰＥＮＡＮＡHs3UEctH3z
HashMap<String, Integer> count = new HashMap<String, Integer>();265Please respect copyright.ＰＥＮＡＮＡfyvrf42CIQ
// Count the number of occurrences of each word using a hashmap265Please respect copyright.ＰＥＮＡＮＡiAedWTKWpS
for (String word : words) {265Please respect copyright.ＰＥＮＡＮＡ7yiMpO8aTy
Integer countOfTheWord = count.get(word);265Please respect copyright.ＰＥＮＡＮＡYLwlMBHYO1
if (countOfTheWord == null) {265Please respect copyright.ＰＥＮＡＮＡX0PRzpZiHu
count.put(word, 1);265Please respect copyright.ＰＥＮＡＮＡjokuvicuCa
} else {265Please respect copyright.ＰＥＮＡＮＡsUAvsRzWK9
count.put(word, countOfTheWord + 1);265Please respect copyright.ＰＥＮＡＮＡxQ0ulbMhXt
}265Please respect copyright.ＰＥＮＡＮＡiWfwUGPkTn
}265Please respect copyright.ＰＥＮＡＮＡv40SKaH500
// 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 word265Please respect copyright.ＰＥＮＡＮＡtaElZX9QVS
int answer = 0;265Please respect copyright.ＰＥＮＡＮＡkbUuSHfMZN
boolean central = false;265Please respect copyright.ＰＥＮＡＮＡ9SEOKHWM47
for (Map.Entry<String, Integer> entry : count.entrySet()) {265Please respect copyright.ＰＥＮＡＮＡxj1UO5Aai8
String word = entry.getKey();265Please respect copyright.ＰＥＮＡＮＡr2ry9wrkib
int countOfTheWord = entry.getValue();265Please respect copyright.ＰＥＮＡＮＡGoH6j6ozBK
// if the word is a palindrome265Please respect copyright.ＰＥＮＡＮＡRnjFdIOdwp
if (word.charAt(0) == word.charAt(1)) {265Please respect copyright.ＰＥＮＡＮＡyedFToBpCM
if (countOfTheWord % 2 == 0) {265Please respect copyright.ＰＥＮＡＮＡMVtjWnZAdV
answer += countOfTheWord;265Please respect copyright.ＰＥＮＡＮＡBfJlycjnPd
} else {265Please respect copyright.ＰＥＮＡＮＡe3bweFxqRj
answer += countOfTheWord - 1;265Please respect copyright.ＰＥＮＡＮＡQWsjZrqUpM
central = true;265Please respect copyright.ＰＥＮＡＮＡkmA4RvaqZS
}265Please respect copyright.ＰＥＮＡＮＡNsxu68bjv7
// consider a pair of non-palindrome words such that one is the reverse of another265Please respect copyright.ＰＥＮＡＮＡsI1tCuRFzv
} else if (word.charAt(0) < word.charAt(1)) {265Please respect copyright.ＰＥＮＡＮＡIei9nbCn5i
String reversedWord = "" + word.charAt(1) + word.charAt(0);265Please respect copyright.ＰＥＮＡＮＡ74JFFasP1Z
if (count.containsKey(reversedWord)) {265Please respect copyright.ＰＥＮＡＮＡrCty3tcZFg
answer += 2 * Math.min(countOfTheWord, count.get(reversedWord));265Please respect copyright.ＰＥＮＡＮＡHXhxRCm5bY
}265Please respect copyright.ＰＥＮＡＮＡKddutEzwYu
}265Please respect copyright.ＰＥＮＡＮＡaFsaFeBZ3c
}265Please respect copyright.ＰＥＮＡＮＡDV3CJX7NsL
if (central) {265Please respect copyright.ＰＥＮＡＮＡCYIvzO07NN
answer++;265Please respect copyright.ＰＥＮＡＮＡNzVdx3P13e
}265Please respect copyright.ＰＥＮＡＮＡH6mi9jCyix
return 2 * answer;265Please respect copyright.ＰＥＮＡＮＡqmuHHYXHAg
}265Please respect copyright.ＰＥＮＡＮＡ2V9YHaG1ux
}
2: A Two-Dimensional Array Approach
class Solution {265Please respect copyright.ＰＥＮＡＮＡc7jkKqv119
public int longestPalindrome(String[] words) {265Please respect copyright.ＰＥＮＡＮＡGr9camqOCT
final int alphabetSize = 26;265Please respect copyright.ＰＥＮＡＮＡr8naEj2YU4
int[][] count = new int[alphabetSize][alphabetSize];265Please respect copyright.ＰＥＮＡＮＡ0lvDdsdrMR
// Count the number of occurrences of each word using a two-dimensional array. 265Please respect copyright.ＰＥＮＡＮＡe3QajgUSCO
for (String word : words) {265Please respect copyright.ＰＥＮＡＮＡ5UK046MY8S
count[word.charAt(0) - 'a'][word.charAt(1) - 'a']++;265Please respect copyright.ＰＥＮＡＮＡqPGMeg8doa
}265Please respect copyright.ＰＥＮＡＮＡY0Rykv1d8J
// The answer will denote the number of words in the final string and the boolean variable central will denote whether we have a central word265Please respect copyright.ＰＥＮＡＮＡ47hsbgE5du
int answer = 0;265Please respect copyright.ＰＥＮＡＮＡJZv6VFqSk5
boolean central = false;265Please respect copyright.ＰＥＮＡＮＡu23gj1GqW0
for (int i = 0; i < alphabetSize; i++) {265Please respect copyright.ＰＥＮＡＮＡZYT0BOu2it
if (count[i][i] % 2 == 0) {265Please respect copyright.ＰＥＮＡＮＡQju1FeWAFU
answer += count[i][i];265Please respect copyright.ＰＥＮＡＮＡSBUvPN1Onk
} else {265Please respect copyright.ＰＥＮＡＮＡ5lmUN6Kror
answer += count[i][i] - 1;265Please respect copyright.ＰＥＮＡＮＡwAxC6c0lG7
central = true;265Please respect copyright.ＰＥＮＡＮＡWLuIQfRrp9
}265Please respect copyright.ＰＥＮＡＮＡYmabBaoYGW
for (int j = i + 1; j < alphabetSize; j++) {265Please respect copyright.ＰＥＮＡＮＡXONBFOEyTP
answer += 2 * Math.min(count[i][j], count[j][i]);265Please respect copyright.ＰＥＮＡＮＡe5uXRshYvJ
}265Please respect copyright.ＰＥＮＡＮＡwYRnFd95dD
}265Please respect copyright.ＰＥＮＡＮＡnCB97axODy
if (central) {265Please respect copyright.ＰＥＮＡＮＡBuRwmY244u
answer++;265Please respect copyright.ＰＥＮＡＮＡIul9sC08Cc
}265Please respect copyright.ＰＥＮＡＮＡ0e2R5hEA37
return 2 * answer;265Please respect copyright.ＰＥＮＡＮＡwz4Y2v24vP
}265Please respect copyright.ＰＥＮＡＮＡa7SAmQq2qz
}
265Please respect copyright.ＰＥＮＡＮＡtUqyGcZKQQ
