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 {199Please respect copyright.ＰＥＮＡＮＡeSnBv3MO6C
public int longestPalindrome(String[] words) {199Please respect copyright.ＰＥＮＡＮＡQv8iv4ekZk
HashMap<String, Integer> count = new HashMap<String, Integer>();199Please respect copyright.ＰＥＮＡＮＡt3O2Pw11eh
// Count the number of occurrences of each word using a hashmap199Please respect copyright.ＰＥＮＡＮＡSrFZet3WyN
for (String word : words) {199Please respect copyright.ＰＥＮＡＮＡEHamsky8Nd
Integer countOfTheWord = count.get(word);199Please respect copyright.ＰＥＮＡＮＡM85Xo3v0jC
if (countOfTheWord == null) {199Please respect copyright.ＰＥＮＡＮＡBBto0OOVLE
count.put(word, 1);199Please respect copyright.ＰＥＮＡＮＡpALM2is8BC
} else {199Please respect copyright.ＰＥＮＡＮＡUrP5YnERxq
count.put(word, countOfTheWord + 1);199Please respect copyright.ＰＥＮＡＮＡBHxQiL6Zmw
}199Please respect copyright.ＰＥＮＡＮＡXpRapUe5Wi
}199Please respect copyright.ＰＥＮＡＮＡMOtM2Q8REY
// 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 word199Please respect copyright.ＰＥＮＡＮＡ51c2hukChA
int answer = 0;199Please respect copyright.ＰＥＮＡＮＡze7yEhtasE
boolean central = false;199Please respect copyright.ＰＥＮＡＮＡD0VsP7ZkO9
for (Map.Entry<String, Integer> entry : count.entrySet()) {199Please respect copyright.ＰＥＮＡＮＡ33DI3cNrCQ
String word = entry.getKey();199Please respect copyright.ＰＥＮＡＮＡdMFnCoFV9T
int countOfTheWord = entry.getValue();199Please respect copyright.ＰＥＮＡＮＡznnosVy647
// if the word is a palindrome199Please respect copyright.ＰＥＮＡＮＡZqeLdVf7Pb
if (word.charAt(0) == word.charAt(1)) {199Please respect copyright.ＰＥＮＡＮＡKGh1s1sR3n
if (countOfTheWord % 2 == 0) {199Please respect copyright.ＰＥＮＡＮＡNIZiyCqiuz
answer += countOfTheWord;199Please respect copyright.ＰＥＮＡＮＡckghCYUPVN
} else {199Please respect copyright.ＰＥＮＡＮＡXIN252jL09
answer += countOfTheWord - 1;199Please respect copyright.ＰＥＮＡＮＡzY0IHsJifC
central = true;199Please respect copyright.ＰＥＮＡＮＡFmCla7SNLT
}199Please respect copyright.ＰＥＮＡＮＡuQLlE3jq64
// consider a pair of non-palindrome words such that one is the reverse of another199Please respect copyright.ＰＥＮＡＮＡ3RbbfbmVHP
} else if (word.charAt(0) < word.charAt(1)) {199Please respect copyright.ＰＥＮＡＮＡkaBB9hCNjQ
String reversedWord = "" + word.charAt(1) + word.charAt(0);199Please respect copyright.ＰＥＮＡＮＡZUgO5Wt7wU
if (count.containsKey(reversedWord)) {199Please respect copyright.ＰＥＮＡＮＡWNnNKnUQ62
answer += 2 * Math.min(countOfTheWord, count.get(reversedWord));199Please respect copyright.ＰＥＮＡＮＡDFBGAGzfJZ
}199Please respect copyright.ＰＥＮＡＮＡA8Ufy24KKR
}199Please respect copyright.ＰＥＮＡＮＡsDDpRhpM6Q
}199Please respect copyright.ＰＥＮＡＮＡSvZWAnOmxy
if (central) {199Please respect copyright.ＰＥＮＡＮＡKkEoAPWKoY
answer++;199Please respect copyright.ＰＥＮＡＮＡSDjjOG8cU5
}199Please respect copyright.ＰＥＮＡＮＡ66kK2NKJb2
return 2 * answer;199Please respect copyright.ＰＥＮＡＮＡH9vgtCUNYz
}199Please respect copyright.ＰＥＮＡＮＡ9qEvyawwET
}
2: A Two-Dimensional Array Approach
class Solution {199Please respect copyright.ＰＥＮＡＮＡTKETeX3pKT
public int longestPalindrome(String[] words) {199Please respect copyright.ＰＥＮＡＮＡakHcXRPf1K
final int alphabetSize = 26;199Please respect copyright.ＰＥＮＡＮＡo4hC53Q1pp
int[][] count = new int[alphabetSize][alphabetSize];199Please respect copyright.ＰＥＮＡＮＡQ6mlRrHusX
// Count the number of occurrences of each word using a two-dimensional array. 199Please respect copyright.ＰＥＮＡＮＡSPAUQE70YY
for (String word : words) {199Please respect copyright.ＰＥＮＡＮＡxel7eHOAIl
count[word.charAt(0) - 'a'][word.charAt(1) - 'a']++;199Please respect copyright.ＰＥＮＡＮＡgjH0bZiLoS
}199Please respect copyright.ＰＥＮＡＮＡyDqZOP35NR
// The answer will denote the number of words in the final string and the boolean variable central will denote whether we have a central word199Please respect copyright.ＰＥＮＡＮＡouOwgibh7J
int answer = 0;199Please respect copyright.ＰＥＮＡＮＡQvB7MoGXG5
boolean central = false;199Please respect copyright.ＰＥＮＡＮＡ43xdsm08gH
for (int i = 0; i < alphabetSize; i++) {199Please respect copyright.ＰＥＮＡＮＡ1ny7E0a4JO
if (count[i][i] % 2 == 0) {199Please respect copyright.ＰＥＮＡＮＡ3TQRaYybeP
answer += count[i][i];199Please respect copyright.ＰＥＮＡＮＡ9kLMQn7yeG
} else {199Please respect copyright.ＰＥＮＡＮＡVgEc9A9dnh
answer += count[i][i] - 1;199Please respect copyright.ＰＥＮＡＮＡVhw3zflELA
central = true;199Please respect copyright.ＰＥＮＡＮＡQQCCbLfVJm
}199Please respect copyright.ＰＥＮＡＮＡoNTqiGfOBo
for (int j = i + 1; j < alphabetSize; j++) {199Please respect copyright.ＰＥＮＡＮＡCdC2uATiqk
answer += 2 * Math.min(count[i][j], count[j][i]);199Please respect copyright.ＰＥＮＡＮＡwz3zDYsKPh
}199Please respect copyright.ＰＥＮＡＮＡ5MUqXRi7XT
}199Please respect copyright.ＰＥＮＡＮＡZFQQclhhfh
if (central) {199Please respect copyright.ＰＥＮＡＮＡEDpl6sCPn4
answer++;199Please respect copyright.ＰＥＮＡＮＡnBRPpx5cFS
}199Please respect copyright.ＰＥＮＡＮＡQo4c4hpD1B
return 2 * answer;199Please respect copyright.ＰＥＮＡＮＡVr2P13dtaA
}199Please respect copyright.ＰＥＮＡＮＡj1p3rmIA3X
}
199Please respect copyright.ＰＥＮＡＮＡTM5BkemAVc
