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 {279Please respect copyright.ＰＥＮＡＮＡqmoCn3PaGe
public int longestPalindrome(String[] words) {279Please respect copyright.ＰＥＮＡＮＡsvY524hB6x
HashMap<String, Integer> count = new HashMap<String, Integer>();279Please respect copyright.ＰＥＮＡＮＡtGMIhodbrx
// Count the number of occurrences of each word using a hashmap279Please respect copyright.ＰＥＮＡＮＡ70k4jktaIQ
for (String word : words) {279Please respect copyright.ＰＥＮＡＮＡAv2WaADSod
Integer countOfTheWord = count.get(word);279Please respect copyright.ＰＥＮＡＮＡFqItxfUUwo
if (countOfTheWord == null) {279Please respect copyright.ＰＥＮＡＮＡZEnSA64md0
count.put(word, 1);279Please respect copyright.ＰＥＮＡＮＡWgDAmU3Bpt
} else {279Please respect copyright.ＰＥＮＡＮＡYENV6svFFQ
count.put(word, countOfTheWord + 1);279Please respect copyright.ＰＥＮＡＮＡQG8NVZycCx
}279Please respect copyright.ＰＥＮＡＮＡetmulQg7cv
}279Please respect copyright.ＰＥＮＡＮＡl4MLw0vQTR
// 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 word279Please respect copyright.ＰＥＮＡＮＡTFGpeoz3Ws
int answer = 0;279Please respect copyright.ＰＥＮＡＮＡpanPSFrhwY
boolean central = false;279Please respect copyright.ＰＥＮＡＮＡuu082kP1dO
for (Map.Entry<String, Integer> entry : count.entrySet()) {279Please respect copyright.ＰＥＮＡＮＡarRFdoPJ8X
String word = entry.getKey();279Please respect copyright.ＰＥＮＡＮＡ0vRgBo996U
int countOfTheWord = entry.getValue();279Please respect copyright.ＰＥＮＡＮＡuUKG637KdV
// if the word is a palindrome279Please respect copyright.ＰＥＮＡＮＡNZpe63unC7
if (word.charAt(0) == word.charAt(1)) {279Please respect copyright.ＰＥＮＡＮＡHbQfvqq03h
if (countOfTheWord % 2 == 0) {279Please respect copyright.ＰＥＮＡＮＡL46sISNRHI
answer += countOfTheWord;279Please respect copyright.ＰＥＮＡＮＡw26bj3hJ3K
} else {279Please respect copyright.ＰＥＮＡＮＡwdWwhubAig
answer += countOfTheWord - 1;279Please respect copyright.ＰＥＮＡＮＡ350WVVIXRl
central = true;279Please respect copyright.ＰＥＮＡＮＡBulFW7lzAn
}279Please respect copyright.ＰＥＮＡＮＡEbAAPQEobp
// consider a pair of non-palindrome words such that one is the reverse of another279Please respect copyright.ＰＥＮＡＮＡwZw5u2YMs5
} else if (word.charAt(0) < word.charAt(1)) {279Please respect copyright.ＰＥＮＡＮＡ4MJ5AnXqq5
String reversedWord = "" + word.charAt(1) + word.charAt(0);279Please respect copyright.ＰＥＮＡＮＡNu8uiUaP0h
if (count.containsKey(reversedWord)) {279Please respect copyright.ＰＥＮＡＮＡVKByczeCDW
answer += 2 * Math.min(countOfTheWord, count.get(reversedWord));279Please respect copyright.ＰＥＮＡＮＡjn6jX2tATG
}279Please respect copyright.ＰＥＮＡＮＡ0ZbUiRnIDt
}279Please respect copyright.ＰＥＮＡＮＡBYgbkdeWZb
}279Please respect copyright.ＰＥＮＡＮＡkuL5ETfRDU
if (central) {279Please respect copyright.ＰＥＮＡＮＡtWqGb573se
answer++;279Please respect copyright.ＰＥＮＡＮＡ8gGyS5YRNs
}279Please respect copyright.ＰＥＮＡＮＡB8oZDeYqaF
return 2 * answer;279Please respect copyright.ＰＥＮＡＮＡfHh0hIPzx1
}279Please respect copyright.ＰＥＮＡＮＡs1noZfAMzW
}
2: A Two-Dimensional Array Approach
class Solution {279Please respect copyright.ＰＥＮＡＮＡbwCvfCI20S
public int longestPalindrome(String[] words) {279Please respect copyright.ＰＥＮＡＮＡTdrsdZSoqb
final int alphabetSize = 26;279Please respect copyright.ＰＥＮＡＮＡuaWA6sR7Pz
int[][] count = new int[alphabetSize][alphabetSize];279Please respect copyright.ＰＥＮＡＮＡltUmojfHow
// Count the number of occurrences of each word using a two-dimensional array. 279Please respect copyright.ＰＥＮＡＮＡLIngEZx2lz
for (String word : words) {279Please respect copyright.ＰＥＮＡＮＡhWWq3haVA8
count[word.charAt(0) - 'a'][word.charAt(1) - 'a']++;279Please respect copyright.ＰＥＮＡＮＡFiTsRN8O1i
}279Please respect copyright.ＰＥＮＡＮＡt4tbUwLFNU
// The answer will denote the number of words in the final string and the boolean variable central will denote whether we have a central word279Please respect copyright.ＰＥＮＡＮＡMFF62ws4IM
int answer = 0;279Please respect copyright.ＰＥＮＡＮＡiw9NS0iHSQ
boolean central = false;279Please respect copyright.ＰＥＮＡＮＡvqFaoCLfc9
for (int i = 0; i < alphabetSize; i++) {279Please respect copyright.ＰＥＮＡＮＡmdqZwD1cOY
if (count[i][i] % 2 == 0) {279Please respect copyright.ＰＥＮＡＮＡslZXYfRnT1
answer += count[i][i];279Please respect copyright.ＰＥＮＡＮＡebc7SQMIMk
} else {279Please respect copyright.ＰＥＮＡＮＡbiom6scmjl
answer += count[i][i] - 1;279Please respect copyright.ＰＥＮＡＮＡaIepLmUsAe
central = true;279Please respect copyright.ＰＥＮＡＮＡ0YsRxK8Gtb
}279Please respect copyright.ＰＥＮＡＮＡar5EKwMTkA
for (int j = i + 1; j < alphabetSize; j++) {279Please respect copyright.ＰＥＮＡＮＡOQZ7X9m9WE
answer += 2 * Math.min(count[i][j], count[j][i]);279Please respect copyright.ＰＥＮＡＮＡPZlVC0XXUo
}279Please respect copyright.ＰＥＮＡＮＡJuzk237J9y
}279Please respect copyright.ＰＥＮＡＮＡSqsuib7Vrh
if (central) {279Please respect copyright.ＰＥＮＡＮＡTf0EUMCTP2
answer++;279Please respect copyright.ＰＥＮＡＮＡASRX8moZH2
}279Please respect copyright.ＰＥＮＡＮＡQulJKB0RCj
return 2 * answer;279Please respect copyright.ＰＥＮＡＮＡpAKuAPxJdy
}279Please respect copyright.ＰＥＮＡＮＡ2l6qYBI5e1
}
279Please respect copyright.ＰＥＮＡＮＡLFDe8ZMvZm
