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 {143Please respect copyright.ＰＥＮＡＮＡkpff22YPRG
public int longestPalindrome(String[] words) {143Please respect copyright.ＰＥＮＡＮＡyYPwpqlpPP
HashMap<String, Integer> count = new HashMap<String, Integer>();143Please respect copyright.ＰＥＮＡＮＡsZdu3YK4ei
// Count the number of occurrences of each word using a hashmap143Please respect copyright.ＰＥＮＡＮＡAJqFoql1OX
for (String word : words) {143Please respect copyright.ＰＥＮＡＮＡRwN1Mjdn3M
Integer countOfTheWord = count.get(word);143Please respect copyright.ＰＥＮＡＮＡWXSEJQXTUV
if (countOfTheWord == null) {143Please respect copyright.ＰＥＮＡＮＡi28FsHlhaR
count.put(word, 1);143Please respect copyright.ＰＥＮＡＮＡVuEymLONko
} else {143Please respect copyright.ＰＥＮＡＮＡzwi2b7OCq6
count.put(word, countOfTheWord + 1);143Please respect copyright.ＰＥＮＡＮＡLhlgINlYow
}143Please respect copyright.ＰＥＮＡＮＡ3lb0wWR87d
}143Please respect copyright.ＰＥＮＡＮＡU33Jxw8HtQ
// 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 word143Please respect copyright.ＰＥＮＡＮＡf3SLnVLJEw
int answer = 0;143Please respect copyright.ＰＥＮＡＮＡLc2C2Y4rpT
boolean central = false;143Please respect copyright.ＰＥＮＡＮＡM6hxxU0x6j
for (Map.Entry<String, Integer> entry : count.entrySet()) {143Please respect copyright.ＰＥＮＡＮＡwLXvfStz7x
String word = entry.getKey();143Please respect copyright.ＰＥＮＡＮＡF78vS7vEgH
int countOfTheWord = entry.getValue();143Please respect copyright.ＰＥＮＡＮＡaHK2d1tfW7
// if the word is a palindrome143Please respect copyright.ＰＥＮＡＮＡeIy73fRmVm
if (word.charAt(0) == word.charAt(1)) {143Please respect copyright.ＰＥＮＡＮＡnKQvJtgfb1
if (countOfTheWord % 2 == 0) {143Please respect copyright.ＰＥＮＡＮＡhkxkXcVpVt
answer += countOfTheWord;143Please respect copyright.ＰＥＮＡＮＡOGiJcGi9en
} else {143Please respect copyright.ＰＥＮＡＮＡ961emUABDs
answer += countOfTheWord - 1;143Please respect copyright.ＰＥＮＡＮＡ2ERf158w4G
central = true;143Please respect copyright.ＰＥＮＡＮＡnAagtHaEXN
}143Please respect copyright.ＰＥＮＡＮＡpbD8Ilo7cG
// consider a pair of non-palindrome words such that one is the reverse of another143Please respect copyright.ＰＥＮＡＮＡYDIw9pGgaq
} else if (word.charAt(0) < word.charAt(1)) {143Please respect copyright.ＰＥＮＡＮＡuXk9DYUVKR
String reversedWord = "" + word.charAt(1) + word.charAt(0);143Please respect copyright.ＰＥＮＡＮＡY9ydo9A0nt
if (count.containsKey(reversedWord)) {143Please respect copyright.ＰＥＮＡＮＡyfN0qSWb5A
answer += 2 * Math.min(countOfTheWord, count.get(reversedWord));143Please respect copyright.ＰＥＮＡＮＡWily9W0btB
}143Please respect copyright.ＰＥＮＡＮＡ7Lrv56kxm1
}143Please respect copyright.ＰＥＮＡＮＡhtJHQNNM6z
}143Please respect copyright.ＰＥＮＡＮＡxfSHTcuQRr
if (central) {143Please respect copyright.ＰＥＮＡＮＡctAyPYByX4
answer++;143Please respect copyright.ＰＥＮＡＮＡv4Rq2OdcTw
}143Please respect copyright.ＰＥＮＡＮＡSB45OgbD87
return 2 * answer;143Please respect copyright.ＰＥＮＡＮＡIZlHZgL8oE
}143Please respect copyright.ＰＥＮＡＮＡLFRASr3iOo
}
2: A Two-Dimensional Array Approach
class Solution {143Please respect copyright.ＰＥＮＡＮＡeaUV2GO1Gr
public int longestPalindrome(String[] words) {143Please respect copyright.ＰＥＮＡＮＡ8vL7qn5TXV
final int alphabetSize = 26;143Please respect copyright.ＰＥＮＡＮＡ60OrWFjOC2
int[][] count = new int[alphabetSize][alphabetSize];143Please respect copyright.ＰＥＮＡＮＡj51OsqgIXU
// Count the number of occurrences of each word using a two-dimensional array. 143Please respect copyright.ＰＥＮＡＮＡz1vtQsy5VQ
for (String word : words) {143Please respect copyright.ＰＥＮＡＮＡw6Ti6BIACp
count[word.charAt(0) - 'a'][word.charAt(1) - 'a']++;143Please respect copyright.ＰＥＮＡＮＡhoCecXgcu5
}143Please respect copyright.ＰＥＮＡＮＡmIOVzhQxNF
// The answer will denote the number of words in the final string and the boolean variable central will denote whether we have a central word143Please respect copyright.ＰＥＮＡＮＡVuz6biN1gY
int answer = 0;143Please respect copyright.ＰＥＮＡＮＡIE9b1nmfIZ
boolean central = false;143Please respect copyright.ＰＥＮＡＮＡp7ChMJZk1j
for (int i = 0; i < alphabetSize; i++) {143Please respect copyright.ＰＥＮＡＮＡ0ddQqINNXZ
if (count[i][i] % 2 == 0) {143Please respect copyright.ＰＥＮＡＮＡcVB7k7Uny1
answer += count[i][i];143Please respect copyright.ＰＥＮＡＮＡL4ogjYw2E5
} else {143Please respect copyright.ＰＥＮＡＮＡGQvfLy3Dy6
answer += count[i][i] - 1;143Please respect copyright.ＰＥＮＡＮＡ4yEjtlosDN
central = true;143Please respect copyright.ＰＥＮＡＮＡCJUfZHyT9r
}143Please respect copyright.ＰＥＮＡＮＡWfGnt6cy5s
for (int j = i + 1; j < alphabetSize; j++) {143Please respect copyright.ＰＥＮＡＮＡt9rk4suNGF
answer += 2 * Math.min(count[i][j], count[j][i]);143Please respect copyright.ＰＥＮＡＮＡ1yKPhj5nFN
}143Please respect copyright.ＰＥＮＡＮＡBGG8ILNt6J
}143Please respect copyright.ＰＥＮＡＮＡNbMFXo3zlg
if (central) {143Please respect copyright.ＰＥＮＡＮＡZo5bvHTkJr
answer++;143Please respect copyright.ＰＥＮＡＮＡ8Kzgnl2fTo
}143Please respect copyright.ＰＥＮＡＮＡyCQtKSbiEY
return 2 * answer;143Please respect copyright.ＰＥＮＡＮＡG008ed7QWc
}143Please respect copyright.ＰＥＮＡＮＡAlQ752weo5
}
143Please respect copyright.ＰＥＮＡＮＡtFH56mjNCS
