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 {288Please respect copyright.ＰＥＮＡＮＡF5g5RGf8lx
public int longestPalindrome(String[] words) {288Please respect copyright.ＰＥＮＡＮＡw8wJUosp57
HashMap<String, Integer> count = new HashMap<String, Integer>();288Please respect copyright.ＰＥＮＡＮＡLLYoStGJiO
// Count the number of occurrences of each word using a hashmap288Please respect copyright.ＰＥＮＡＮＡ7Dv7t0KntZ
for (String word : words) {288Please respect copyright.ＰＥＮＡＮＡyba1aTFPnY
Integer countOfTheWord = count.get(word);288Please respect copyright.ＰＥＮＡＮＡaw9YiqEZQV
if (countOfTheWord == null) {288Please respect copyright.ＰＥＮＡＮＡRF98FLXIh9
count.put(word, 1);288Please respect copyright.ＰＥＮＡＮＡhkrfr4puz0
} else {288Please respect copyright.ＰＥＮＡＮＡHlNRcitmZR
count.put(word, countOfTheWord + 1);288Please respect copyright.ＰＥＮＡＮＡiA1zzwiXU1
}288Please respect copyright.ＰＥＮＡＮＡhtfjCvGJOU
}288Please respect copyright.ＰＥＮＡＮＡcx0fafhgD2
// 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 word288Please respect copyright.ＰＥＮＡＮＡ5yFSktozg1
int answer = 0;288Please respect copyright.ＰＥＮＡＮＡkdz3weTIBm
boolean central = false;288Please respect copyright.ＰＥＮＡＮＡgpbX9h869R
for (Map.Entry<String, Integer> entry : count.entrySet()) {288Please respect copyright.ＰＥＮＡＮＡ7f8GD3hgb2
String word = entry.getKey();288Please respect copyright.ＰＥＮＡＮＡf9K58cybBT
int countOfTheWord = entry.getValue();288Please respect copyright.ＰＥＮＡＮＡnfTzXfxxM8
// if the word is a palindrome288Please respect copyright.ＰＥＮＡＮＡdbMhKI01vg
if (word.charAt(0) == word.charAt(1)) {288Please respect copyright.ＰＥＮＡＮＡh5cXT4fRes
if (countOfTheWord % 2 == 0) {288Please respect copyright.ＰＥＮＡＮＡ3F5cAVxUOu
answer += countOfTheWord;288Please respect copyright.ＰＥＮＡＮＡg9wJ8YVIDu
} else {288Please respect copyright.ＰＥＮＡＮＡzlOPPinG8u
answer += countOfTheWord - 1;288Please respect copyright.ＰＥＮＡＮＡvpDXvlsW1P
central = true;288Please respect copyright.ＰＥＮＡＮＡdFqGYNPuFA
}288Please respect copyright.ＰＥＮＡＮＡyH2i4Kfd9U
// consider a pair of non-palindrome words such that one is the reverse of another288Please respect copyright.ＰＥＮＡＮＡzTE3BB3PJE
} else if (word.charAt(0) < word.charAt(1)) {288Please respect copyright.ＰＥＮＡＮＡlGZxe4JOMg
String reversedWord = "" + word.charAt(1) + word.charAt(0);288Please respect copyright.ＰＥＮＡＮＡPtrDnwPdij
if (count.containsKey(reversedWord)) {288Please respect copyright.ＰＥＮＡＮＡYwTDx1uvmB
answer += 2 * Math.min(countOfTheWord, count.get(reversedWord));288Please respect copyright.ＰＥＮＡＮＡoY9Vx9ghko
}288Please respect copyright.ＰＥＮＡＮＡf4bflWuGDg
}288Please respect copyright.ＰＥＮＡＮＡFcXp72BbiT
}288Please respect copyright.ＰＥＮＡＮＡG00eGGjTaA
if (central) {288Please respect copyright.ＰＥＮＡＮＡc442gMgpcl
answer++;288Please respect copyright.ＰＥＮＡＮＡENOb2xbwHP
}288Please respect copyright.ＰＥＮＡＮＡ9zLZlBKmj4
return 2 * answer;288Please respect copyright.ＰＥＮＡＮＡfgbWox8J8u
}288Please respect copyright.ＰＥＮＡＮＡJGLrjoMbOm
}
2: A Two-Dimensional Array Approach
class Solution {288Please respect copyright.ＰＥＮＡＮＡARgwj9AEdV
public int longestPalindrome(String[] words) {288Please respect copyright.ＰＥＮＡＮＡ6GuPjrfK0T
final int alphabetSize = 26;288Please respect copyright.ＰＥＮＡＮＡntZoyXEMjt
int[][] count = new int[alphabetSize][alphabetSize];288Please respect copyright.ＰＥＮＡＮＡnRp9dhRpAc
// Count the number of occurrences of each word using a two-dimensional array. 288Please respect copyright.ＰＥＮＡＮＡIrxCarfv6y
for (String word : words) {288Please respect copyright.ＰＥＮＡＮＡey6fVDfWDb
count[word.charAt(0) - 'a'][word.charAt(1) - 'a']++;288Please respect copyright.ＰＥＮＡＮＡtTktBuM9ht
}288Please respect copyright.ＰＥＮＡＮＡ7FkqXeOCgV
// The answer will denote the number of words in the final string and the boolean variable central will denote whether we have a central word288Please respect copyright.ＰＥＮＡＮＡEvVvmL6VsK
int answer = 0;288Please respect copyright.ＰＥＮＡＮＡajyolU7LiD
boolean central = false;288Please respect copyright.ＰＥＮＡＮＡ6kpTRpChxq
for (int i = 0; i < alphabetSize; i++) {288Please respect copyright.ＰＥＮＡＮＡ0OeU4I4PXo
if (count[i][i] % 2 == 0) {288Please respect copyright.ＰＥＮＡＮＡmZ0XY9dGO7
answer += count[i][i];288Please respect copyright.ＰＥＮＡＮＡJwMSxB0vVh
} else {288Please respect copyright.ＰＥＮＡＮＡ5NLi8ECGwo
answer += count[i][i] - 1;288Please respect copyright.ＰＥＮＡＮＡtS5SBPtpIi
central = true;288Please respect copyright.ＰＥＮＡＮＡ7vECDJ1CZk
}288Please respect copyright.ＰＥＮＡＮＡJ4Yenu9v2l
for (int j = i + 1; j < alphabetSize; j++) {288Please respect copyright.ＰＥＮＡＮＡmCJVt64vDD
answer += 2 * Math.min(count[i][j], count[j][i]);288Please respect copyright.ＰＥＮＡＮＡaTig2nBQjb
}288Please respect copyright.ＰＥＮＡＮＡrCdyCZQfct
}288Please respect copyright.ＰＥＮＡＮＡPUaOE0e8Zm
if (central) {288Please respect copyright.ＰＥＮＡＮＡk8P7sXie1N
answer++;288Please respect copyright.ＰＥＮＡＮＡJOEEEnzDGd
}288Please respect copyright.ＰＥＮＡＮＡVQaz2VpLuJ
return 2 * answer;288Please respect copyright.ＰＥＮＡＮＡsHYXMh0s6v
}288Please respect copyright.ＰＥＮＡＮＡyUkTy7IEAR
}
288Please respect copyright.ＰＥＮＡＮＡsrLR1GzHzy
