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 {241Please respect copyright.ＰＥＮＡＮＡYh95AnOKHh
public int longestPalindrome(String[] words) {241Please respect copyright.ＰＥＮＡＮＡAb8BLGlBCD
HashMap<String, Integer> count = new HashMap<String, Integer>();241Please respect copyright.ＰＥＮＡＮＡO8CNSAHv4T
// Count the number of occurrences of each word using a hashmap241Please respect copyright.ＰＥＮＡＮＡZUAEA875DR
for (String word : words) {241Please respect copyright.ＰＥＮＡＮＡEW5X3ys3Xc
Integer countOfTheWord = count.get(word);241Please respect copyright.ＰＥＮＡＮＡ4hmjlqgZuB
if (countOfTheWord == null) {241Please respect copyright.ＰＥＮＡＮＡvfAkTfNcaF
count.put(word, 1);241Please respect copyright.ＰＥＮＡＮＡHi7YqcQFgk
} else {241Please respect copyright.ＰＥＮＡＮＡL6cTe1j43q
count.put(word, countOfTheWord + 1);241Please respect copyright.ＰＥＮＡＮＡLA37FyOVez
}241Please respect copyright.ＰＥＮＡＮＡgmNHmxE60p
}241Please respect copyright.ＰＥＮＡＮＡo040onvlRp
// 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 word241Please respect copyright.ＰＥＮＡＮＡRUkIf9TVvZ
int answer = 0;241Please respect copyright.ＰＥＮＡＮＡ1Nwg1HLPnq
boolean central = false;241Please respect copyright.ＰＥＮＡＮＡ8nfFC2xx0R
for (Map.Entry<String, Integer> entry : count.entrySet()) {241Please respect copyright.ＰＥＮＡＮＡRwiPpsX01U
String word = entry.getKey();241Please respect copyright.ＰＥＮＡＮＡC0KZxzC58q
int countOfTheWord = entry.getValue();241Please respect copyright.ＰＥＮＡＮＡAYtym6DOwI
// if the word is a palindrome241Please respect copyright.ＰＥＮＡＮＡ38zbiuIPMd
if (word.charAt(0) == word.charAt(1)) {241Please respect copyright.ＰＥＮＡＮＡyUPokwDDps
if (countOfTheWord % 2 == 0) {241Please respect copyright.ＰＥＮＡＮＡchEqJSiI9h
answer += countOfTheWord;241Please respect copyright.ＰＥＮＡＮＡuCXezlKsMx
} else {241Please respect copyright.ＰＥＮＡＮＡw3P6ySas9o
answer += countOfTheWord - 1;241Please respect copyright.ＰＥＮＡＮＡsaBEXnVZCA
central = true;241Please respect copyright.ＰＥＮＡＮＡHowW9wij6r
}241Please respect copyright.ＰＥＮＡＮＡaOiqhiXmTR
// consider a pair of non-palindrome words such that one is the reverse of another241Please respect copyright.ＰＥＮＡＮＡmCx89AP6rE
} else if (word.charAt(0) < word.charAt(1)) {241Please respect copyright.ＰＥＮＡＮＡ8ygCpDcV8o
String reversedWord = "" + word.charAt(1) + word.charAt(0);241Please respect copyright.ＰＥＮＡＮＡuaAqweI0tO
if (count.containsKey(reversedWord)) {241Please respect copyright.ＰＥＮＡＮＡTUcV47KyWL
answer += 2 * Math.min(countOfTheWord, count.get(reversedWord));241Please respect copyright.ＰＥＮＡＮＡ9LJ4EQaOVo
}241Please respect copyright.ＰＥＮＡＮＡJPLTtOzZOh
}241Please respect copyright.ＰＥＮＡＮＡHIGw21przM
}241Please respect copyright.ＰＥＮＡＮＡHpf0m42Ngt
if (central) {241Please respect copyright.ＰＥＮＡＮＡjfinXGK4ax
answer++;241Please respect copyright.ＰＥＮＡＮＡoFySvGrlMf
}241Please respect copyright.ＰＥＮＡＮＡjNmJ9M3hwI
return 2 * answer;241Please respect copyright.ＰＥＮＡＮＡOzDGFaG5Ld
}241Please respect copyright.ＰＥＮＡＮＡF6B0i9n54I
}
2: A Two-Dimensional Array Approach
class Solution {241Please respect copyright.ＰＥＮＡＮＡqiI1qLblPR
public int longestPalindrome(String[] words) {241Please respect copyright.ＰＥＮＡＮＡWdOFf6q3d9
final int alphabetSize = 26;241Please respect copyright.ＰＥＮＡＮＡwTd3w4Vs5A
int[][] count = new int[alphabetSize][alphabetSize];241Please respect copyright.ＰＥＮＡＮＡni2THBcrbz
// Count the number of occurrences of each word using a two-dimensional array. 241Please respect copyright.ＰＥＮＡＮＡYjEjFCNoCH
for (String word : words) {241Please respect copyright.ＰＥＮＡＮＡxrMhwvlTGE
count[word.charAt(0) - 'a'][word.charAt(1) - 'a']++;241Please respect copyright.ＰＥＮＡＮＡ7RD9KDo3ak
}241Please respect copyright.ＰＥＮＡＮＡ2I26WCsQK1
// The answer will denote the number of words in the final string and the boolean variable central will denote whether we have a central word241Please respect copyright.ＰＥＮＡＮＡsACeWugvaY
int answer = 0;241Please respect copyright.ＰＥＮＡＮＡENzP1SPgny
boolean central = false;241Please respect copyright.ＰＥＮＡＮＡcuHSaKMB3D
for (int i = 0; i < alphabetSize; i++) {241Please respect copyright.ＰＥＮＡＮＡFT8j7q3Iym
if (count[i][i] % 2 == 0) {241Please respect copyright.ＰＥＮＡＮＡS5QKQAFzVQ
answer += count[i][i];241Please respect copyright.ＰＥＮＡＮＡTfvKQu26ZR
} else {241Please respect copyright.ＰＥＮＡＮＡuULAMj0v16
answer += count[i][i] - 1;241Please respect copyright.ＰＥＮＡＮＡQaaMPdDLWC
central = true;241Please respect copyright.ＰＥＮＡＮＡxWVjqjuek9
}241Please respect copyright.ＰＥＮＡＮＡAWMEK9jp4W
for (int j = i + 1; j < alphabetSize; j++) {241Please respect copyright.ＰＥＮＡＮＡi9VD87vmG5
answer += 2 * Math.min(count[i][j], count[j][i]);241Please respect copyright.ＰＥＮＡＮＡ2rysN4ILDm
}241Please respect copyright.ＰＥＮＡＮＡpxnuFyL8EE
}241Please respect copyright.ＰＥＮＡＮＡ5BNunEmyL8
if (central) {241Please respect copyright.ＰＥＮＡＮＡZWBfrubKA5
answer++;241Please respect copyright.ＰＥＮＡＮＡ2LO2AJWx1C
}241Please respect copyright.ＰＥＮＡＮＡF6u53sVJMN
return 2 * answer;241Please respect copyright.ＰＥＮＡＮＡVHgM5UjhPy
}241Please respect copyright.ＰＥＮＡＮＡbhoI5vUB90
}
241Please respect copyright.ＰＥＮＡＮＡfBhiKydIoU
