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 {168Please respect copyright.ＰＥＮＡＮＡwetlRFkfYr
public int longestPalindrome(String[] words) {168Please respect copyright.ＰＥＮＡＮＡtOJdWHNmjJ
HashMap<String, Integer> count = new HashMap<String, Integer>();168Please respect copyright.ＰＥＮＡＮＡ5NR7QVvrNv
// Count the number of occurrences of each word using a hashmap168Please respect copyright.ＰＥＮＡＮＡy3fFghr7o6
for (String word : words) {168Please respect copyright.ＰＥＮＡＮＡPi3QZMWOHd
Integer countOfTheWord = count.get(word);168Please respect copyright.ＰＥＮＡＮＡebaGAHEXAF
if (countOfTheWord == null) {168Please respect copyright.ＰＥＮＡＮＡcRMZNzemwi
count.put(word, 1);168Please respect copyright.ＰＥＮＡＮＡoXhIumEEeQ
} else {168Please respect copyright.ＰＥＮＡＮＡYHTnKucJYm
count.put(word, countOfTheWord + 1);168Please respect copyright.ＰＥＮＡＮＡkneHRFddXV
}168Please respect copyright.ＰＥＮＡＮＡ6TzTndIolX
}168Please respect copyright.ＰＥＮＡＮＡ4rExhMRUAr
// 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 word168Please respect copyright.ＰＥＮＡＮＡKuuGACJRXr
int answer = 0;168Please respect copyright.ＰＥＮＡＮＡvjWgNdN0Ey
boolean central = false;168Please respect copyright.ＰＥＮＡＮＡPdWBJyiApr
for (Map.Entry<String, Integer> entry : count.entrySet()) {168Please respect copyright.ＰＥＮＡＮＡimnxfjZo6Z
String word = entry.getKey();168Please respect copyright.ＰＥＮＡＮＡsahWFGF2dj
int countOfTheWord = entry.getValue();168Please respect copyright.ＰＥＮＡＮＡNV7PkUwdRO
// if the word is a palindrome168Please respect copyright.ＰＥＮＡＮＡcJwB0qj1TD
if (word.charAt(0) == word.charAt(1)) {168Please respect copyright.ＰＥＮＡＮＡ3PN315PQWu
if (countOfTheWord % 2 == 0) {168Please respect copyright.ＰＥＮＡＮＡETza57ia8Z
answer += countOfTheWord;168Please respect copyright.ＰＥＮＡＮＡS4R41FPbwM
} else {168Please respect copyright.ＰＥＮＡＮＡRpt2OeDNXA
answer += countOfTheWord - 1;168Please respect copyright.ＰＥＮＡＮＡhhOD8BmNwk
central = true;168Please respect copyright.ＰＥＮＡＮＡTnWQAdrAao
}168Please respect copyright.ＰＥＮＡＮＡohtQPzerUY
// consider a pair of non-palindrome words such that one is the reverse of another168Please respect copyright.ＰＥＮＡＮＡHU2f24QxY7
} else if (word.charAt(0) < word.charAt(1)) {168Please respect copyright.ＰＥＮＡＮＡv95vdA2xDQ
String reversedWord = "" + word.charAt(1) + word.charAt(0);168Please respect copyright.ＰＥＮＡＮＡdKl129DiZQ
if (count.containsKey(reversedWord)) {168Please respect copyright.ＰＥＮＡＮＡ1Jj4ufaEbI
answer += 2 * Math.min(countOfTheWord, count.get(reversedWord));168Please respect copyright.ＰＥＮＡＮＡW7s5cIyJN3
}168Please respect copyright.ＰＥＮＡＮＡnXNhPVzPdl
}168Please respect copyright.ＰＥＮＡＮＡrVdc4GYkns
}168Please respect copyright.ＰＥＮＡＮＡiczivSmZEp
if (central) {168Please respect copyright.ＰＥＮＡＮＡ7Bz2k9Zlbs
answer++;168Please respect copyright.ＰＥＮＡＮＡDdQcqAczJV
}168Please respect copyright.ＰＥＮＡＮＡgzcKcaOPl1
return 2 * answer;168Please respect copyright.ＰＥＮＡＮＡb0yBtfUeQY
}168Please respect copyright.ＰＥＮＡＮＡRroiGOtkZ8
}
2: A Two-Dimensional Array Approach
class Solution {168Please respect copyright.ＰＥＮＡＮＡjJBd5IqyeR
public int longestPalindrome(String[] words) {168Please respect copyright.ＰＥＮＡＮＡ6Foqfp7GWE
final int alphabetSize = 26;168Please respect copyright.ＰＥＮＡＮＡNVtfwPEkA2
int[][] count = new int[alphabetSize][alphabetSize];168Please respect copyright.ＰＥＮＡＮＡ6kwkpmu31Q
// Count the number of occurrences of each word using a two-dimensional array. 168Please respect copyright.ＰＥＮＡＮＡ1MtnC7TRSF
for (String word : words) {168Please respect copyright.ＰＥＮＡＮＡJY5ChfQksK
count[word.charAt(0) - 'a'][word.charAt(1) - 'a']++;168Please respect copyright.ＰＥＮＡＮＡwJnhIKLb1S
}168Please respect copyright.ＰＥＮＡＮＡfsi7HO4fzc
// The answer will denote the number of words in the final string and the boolean variable central will denote whether we have a central word168Please respect copyright.ＰＥＮＡＮＡJ5FYUiWWXw
int answer = 0;168Please respect copyright.ＰＥＮＡＮＡcC0qrl5Msn
boolean central = false;168Please respect copyright.ＰＥＮＡＮＡ7aUk8QrwPL
for (int i = 0; i < alphabetSize; i++) {168Please respect copyright.ＰＥＮＡＮＡ6Jm5c9FMcU
if (count[i][i] % 2 == 0) {168Please respect copyright.ＰＥＮＡＮＡ6Fkrb7Jw0s
answer += count[i][i];168Please respect copyright.ＰＥＮＡＮＡFD0nmu4M9c
} else {168Please respect copyright.ＰＥＮＡＮＡX0fj9pZlXI
answer += count[i][i] - 1;168Please respect copyright.ＰＥＮＡＮＡumVqKgzNtp
central = true;168Please respect copyright.ＰＥＮＡＮＡMh3BbsXHAm
}168Please respect copyright.ＰＥＮＡＮＡQoCEGMpXUy
for (int j = i + 1; j < alphabetSize; j++) {168Please respect copyright.ＰＥＮＡＮＡljS00zJPst
answer += 2 * Math.min(count[i][j], count[j][i]);168Please respect copyright.ＰＥＮＡＮＡdes29wpxgs
}168Please respect copyright.ＰＥＮＡＮＡXj9U4TXJu3
}168Please respect copyright.ＰＥＮＡＮＡlnxiY8F0LA
if (central) {168Please respect copyright.ＰＥＮＡＮＡ7dMcEcpIsc
answer++;168Please respect copyright.ＰＥＮＡＮＡXCedATvKtG
}168Please respect copyright.ＰＥＮＡＮＡyBuUVKHPXY
return 2 * answer;168Please respect copyright.ＰＥＮＡＮＡWbHRiM36cK
}168Please respect copyright.ＰＥＮＡＮＡkNOL454ESl
}
168Please respect copyright.ＰＥＮＡＮＡ9SjL1dN9FK
