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 {237Please respect copyright.ＰＥＮＡＮＡYywTPkjVoF
public int longestPalindrome(String[] words) {237Please respect copyright.ＰＥＮＡＮＡhKwBHChNy7
HashMap<String, Integer> count = new HashMap<String, Integer>();237Please respect copyright.ＰＥＮＡＮＡNp8EVUF9Yy
// Count the number of occurrences of each word using a hashmap237Please respect copyright.ＰＥＮＡＮＡ389vzTcG34
for (String word : words) {237Please respect copyright.ＰＥＮＡＮＡZBjMMBWQ30
Integer countOfTheWord = count.get(word);237Please respect copyright.ＰＥＮＡＮＡgSrIQwUdqW
if (countOfTheWord == null) {237Please respect copyright.ＰＥＮＡＮＡWqnIoiFJHL
count.put(word, 1);237Please respect copyright.ＰＥＮＡＮＡDdi0Y945Sw
} else {237Please respect copyright.ＰＥＮＡＮＡR3gsFWf5rX
count.put(word, countOfTheWord + 1);237Please respect copyright.ＰＥＮＡＮＡsKXZvN9rZP
}237Please respect copyright.ＰＥＮＡＮＡEW64SMlcDx
}237Please respect copyright.ＰＥＮＡＮＡ3FCTz4ScuS
// 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 word237Please respect copyright.ＰＥＮＡＮＡhxCd9BSqum
int answer = 0;237Please respect copyright.ＰＥＮＡＮＡiGiAVEEUwy
boolean central = false;237Please respect copyright.ＰＥＮＡＮＡCSOhaVaBbW
for (Map.Entry<String, Integer> entry : count.entrySet()) {237Please respect copyright.ＰＥＮＡＮＡZIj8rkXiMT
String word = entry.getKey();237Please respect copyright.ＰＥＮＡＮＡOkUxz4ZAcQ
int countOfTheWord = entry.getValue();237Please respect copyright.ＰＥＮＡＮＡqj9fr9HIQu
// if the word is a palindrome237Please respect copyright.ＰＥＮＡＮＡUkJhStS86E
if (word.charAt(0) == word.charAt(1)) {237Please respect copyright.ＰＥＮＡＮＡb6xTmd1Aoy
if (countOfTheWord % 2 == 0) {237Please respect copyright.ＰＥＮＡＮＡGNeEmWiJSE
answer += countOfTheWord;237Please respect copyright.ＰＥＮＡＮＡvWnFMIojrV
} else {237Please respect copyright.ＰＥＮＡＮＡTMEILYU1O9
answer += countOfTheWord - 1;237Please respect copyright.ＰＥＮＡＮＡ6WHRe8MZFA
central = true;237Please respect copyright.ＰＥＮＡＮＡbqYmjbkbyX
}237Please respect copyright.ＰＥＮＡＮＡcl8Xo2iGTf
// consider a pair of non-palindrome words such that one is the reverse of another237Please respect copyright.ＰＥＮＡＮＡYlPWH4vmWj
} else if (word.charAt(0) < word.charAt(1)) {237Please respect copyright.ＰＥＮＡＮＡXSZShF0JEW
String reversedWord = "" + word.charAt(1) + word.charAt(0);237Please respect copyright.ＰＥＮＡＮＡwnOwGvsLb1
if (count.containsKey(reversedWord)) {237Please respect copyright.ＰＥＮＡＮＡDZkFLWzFoY
answer += 2 * Math.min(countOfTheWord, count.get(reversedWord));237Please respect copyright.ＰＥＮＡＮＡcI0Jsz6G8N
}237Please respect copyright.ＰＥＮＡＮＡgOL5TNgK8D
}237Please respect copyright.ＰＥＮＡＮＡRXsVof40Kq
}237Please respect copyright.ＰＥＮＡＮＡaiGNY8CZq0
if (central) {237Please respect copyright.ＰＥＮＡＮＡLurZxMdhup
answer++;237Please respect copyright.ＰＥＮＡＮＡyzh0ne9xa5
}237Please respect copyright.ＰＥＮＡＮＡmNMcEM8YcO
return 2 * answer;237Please respect copyright.ＰＥＮＡＮＡclckYZRMln
}237Please respect copyright.ＰＥＮＡＮＡUh3AKGH4Xe
}
2: A Two-Dimensional Array Approach
class Solution {237Please respect copyright.ＰＥＮＡＮＡbvqwXqmlmK
public int longestPalindrome(String[] words) {237Please respect copyright.ＰＥＮＡＮＡu500wyaQvp
final int alphabetSize = 26;237Please respect copyright.ＰＥＮＡＮＡG1QD9AJY62
int[][] count = new int[alphabetSize][alphabetSize];237Please respect copyright.ＰＥＮＡＮＡXOnWN294JS
// Count the number of occurrences of each word using a two-dimensional array. 237Please respect copyright.ＰＥＮＡＮＡT5LPB0vQqw
for (String word : words) {237Please respect copyright.ＰＥＮＡＮＡBJcrZAeb8f
count[word.charAt(0) - 'a'][word.charAt(1) - 'a']++;237Please respect copyright.ＰＥＮＡＮＡpP9SKoGgqt
}237Please respect copyright.ＰＥＮＡＮＡ6Rnpppp3Xl
// The answer will denote the number of words in the final string and the boolean variable central will denote whether we have a central word237Please respect copyright.ＰＥＮＡＮＡNg0KzRcWuW
int answer = 0;237Please respect copyright.ＰＥＮＡＮＡ57VegD5qN0
boolean central = false;237Please respect copyright.ＰＥＮＡＮＡyXH3IZunhv
for (int i = 0; i < alphabetSize; i++) {237Please respect copyright.ＰＥＮＡＮＡiOESqhU4i1
if (count[i][i] % 2 == 0) {237Please respect copyright.ＰＥＮＡＮＡMjPn4iiSWB
answer += count[i][i];237Please respect copyright.ＰＥＮＡＮＡKKBNOi9Qj7
} else {237Please respect copyright.ＰＥＮＡＮＡWMYCYrLCqW
answer += count[i][i] - 1;237Please respect copyright.ＰＥＮＡＮＡMjm0nlnS6b
central = true;237Please respect copyright.ＰＥＮＡＮＡrNGmViEbj0
}237Please respect copyright.ＰＥＮＡＮＡAybZM1sD48
for (int j = i + 1; j < alphabetSize; j++) {237Please respect copyright.ＰＥＮＡＮＡ444T21CdIi
answer += 2 * Math.min(count[i][j], count[j][i]);237Please respect copyright.ＰＥＮＡＮＡ2nPH9CqhUc
}237Please respect copyright.ＰＥＮＡＮＡVzzFERLSAR
}237Please respect copyright.ＰＥＮＡＮＡeObrA9i39j
if (central) {237Please respect copyright.ＰＥＮＡＮＡZhheSpgYn8
answer++;237Please respect copyright.ＰＥＮＡＮＡHYWSYL80M9
}237Please respect copyright.ＰＥＮＡＮＡXCnWGpmtVP
return 2 * answer;237Please respect copyright.ＰＥＮＡＮＡ0dXNeutO3D
}237Please respect copyright.ＰＥＮＡＮＡvFI3XYpwBS
}
237Please respect copyright.ＰＥＮＡＮＡ6ABVCZxSth
