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 {182Please respect copyright.ＰＥＮＡＮＡRxVjcBKdQX
public int longestPalindrome(String[] words) {182Please respect copyright.ＰＥＮＡＮＡfXB1z4MqjL
HashMap<String, Integer> count = new HashMap<String, Integer>();182Please respect copyright.ＰＥＮＡＮＡ28PMgG4Xwg
// Count the number of occurrences of each word using a hashmap182Please respect copyright.ＰＥＮＡＮＡdo4G4TVcIV
for (String word : words) {182Please respect copyright.ＰＥＮＡＮＡxV2v2a3s0b
Integer countOfTheWord = count.get(word);182Please respect copyright.ＰＥＮＡＮＡWxmsoayZ8z
if (countOfTheWord == null) {182Please respect copyright.ＰＥＮＡＮＡCeEb8SSeIn
count.put(word, 1);182Please respect copyright.ＰＥＮＡＮＡI9cGMKbPuJ
} else {182Please respect copyright.ＰＥＮＡＮＡs0cgj1aAnA
count.put(word, countOfTheWord + 1);182Please respect copyright.ＰＥＮＡＮＡJ08mvqXdif
}182Please respect copyright.ＰＥＮＡＮＡNSQSzBK3qt
}182Please respect copyright.ＰＥＮＡＮＡIs7dldmCnH
// 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 word182Please respect copyright.ＰＥＮＡＮＡHxJf5BjXYv
int answer = 0;182Please respect copyright.ＰＥＮＡＮＡxSfwvoHOh2
boolean central = false;182Please respect copyright.ＰＥＮＡＮＡNtofu3LiRj
for (Map.Entry<String, Integer> entry : count.entrySet()) {182Please respect copyright.ＰＥＮＡＮＡuxpYugpJtM
String word = entry.getKey();182Please respect copyright.ＰＥＮＡＮＡO7vCD3s4es
int countOfTheWord = entry.getValue();182Please respect copyright.ＰＥＮＡＮＡ66WKqEkGSb
// if the word is a palindrome182Please respect copyright.ＰＥＮＡＮＡ4oAFu8yigV
if (word.charAt(0) == word.charAt(1)) {182Please respect copyright.ＰＥＮＡＮＡgtLC7DFD9m
if (countOfTheWord % 2 == 0) {182Please respect copyright.ＰＥＮＡＮＡC6uYdUPXbP
answer += countOfTheWord;182Please respect copyright.ＰＥＮＡＮＡql1EZ56pq5
} else {182Please respect copyright.ＰＥＮＡＮＡn3sDagdCZV
answer += countOfTheWord - 1;182Please respect copyright.ＰＥＮＡＮＡNeMfaJp60Y
central = true;182Please respect copyright.ＰＥＮＡＮＡz0GNPscIon
}182Please respect copyright.ＰＥＮＡＮＡrQQwhPtVFo
// consider a pair of non-palindrome words such that one is the reverse of another182Please respect copyright.ＰＥＮＡＮＡep3BAD2D9J
} else if (word.charAt(0) < word.charAt(1)) {182Please respect copyright.ＰＥＮＡＮＡLCowEQNhzX
String reversedWord = "" + word.charAt(1) + word.charAt(0);182Please respect copyright.ＰＥＮＡＮＡCOYDoxz5Fm
if (count.containsKey(reversedWord)) {182Please respect copyright.ＰＥＮＡＮＡkw5WLcRmxI
answer += 2 * Math.min(countOfTheWord, count.get(reversedWord));182Please respect copyright.ＰＥＮＡＮＡsfEt9sPpjW
}182Please respect copyright.ＰＥＮＡＮＡoJ2bY4JwOn
}182Please respect copyright.ＰＥＮＡＮＡYvJpgrI0yI
}182Please respect copyright.ＰＥＮＡＮＡYBbwFyLfox
if (central) {182Please respect copyright.ＰＥＮＡＮＡe8pEB6KSqM
answer++;182Please respect copyright.ＰＥＮＡＮＡOERTDL9qGd
}182Please respect copyright.ＰＥＮＡＮＡhzsWigBuJv
return 2 * answer;182Please respect copyright.ＰＥＮＡＮＡkyZTRWWMCF
}182Please respect copyright.ＰＥＮＡＮＡAfqEJdBpmG
}
2: A Two-Dimensional Array Approach
class Solution {182Please respect copyright.ＰＥＮＡＮＡYqd87UuEUr
public int longestPalindrome(String[] words) {182Please respect copyright.ＰＥＮＡＮＡaBcKxieWTd
final int alphabetSize = 26;182Please respect copyright.ＰＥＮＡＮＡf2AzJ5FlAp
int[][] count = new int[alphabetSize][alphabetSize];182Please respect copyright.ＰＥＮＡＮＡrwjvvn7UGU
// Count the number of occurrences of each word using a two-dimensional array. 182Please respect copyright.ＰＥＮＡＮＡCDzlETGU0f
for (String word : words) {182Please respect copyright.ＰＥＮＡＮＡt1Grr0tiOm
count[word.charAt(0) - 'a'][word.charAt(1) - 'a']++;182Please respect copyright.ＰＥＮＡＮＡAlv7TGJt5C
}182Please respect copyright.ＰＥＮＡＮＡyZeF65DvgB
// The answer will denote the number of words in the final string and the boolean variable central will denote whether we have a central word182Please respect copyright.ＰＥＮＡＮＡIv17ch8min
int answer = 0;182Please respect copyright.ＰＥＮＡＮＡBquNi3Jt5r
boolean central = false;182Please respect copyright.ＰＥＮＡＮＡ7xlbOGZ0Xu
for (int i = 0; i < alphabetSize; i++) {182Please respect copyright.ＰＥＮＡＮＡ97mWLPBMhs
if (count[i][i] % 2 == 0) {182Please respect copyright.ＰＥＮＡＮＡSWkFwgLaJq
answer += count[i][i];182Please respect copyright.ＰＥＮＡＮＡbsC2iDc0KO
} else {182Please respect copyright.ＰＥＮＡＮＡBZcfKOikIm
answer += count[i][i] - 1;182Please respect copyright.ＰＥＮＡＮＡUCcYJTDw6I
central = true;182Please respect copyright.ＰＥＮＡＮＡo9l8LaMnRf
}182Please respect copyright.ＰＥＮＡＮＡV6CVZdEXN1
for (int j = i + 1; j < alphabetSize; j++) {182Please respect copyright.ＰＥＮＡＮＡYUkoWze4F1
answer += 2 * Math.min(count[i][j], count[j][i]);182Please respect copyright.ＰＥＮＡＮＡD22WuwOxvY
}182Please respect copyright.ＰＥＮＡＮＡ9VR4FRE3UP
}182Please respect copyright.ＰＥＮＡＮＡ9N63ytgshx
if (central) {182Please respect copyright.ＰＥＮＡＮＡJQhEQeftLd
answer++;182Please respect copyright.ＰＥＮＡＮＡL22r8G70JZ
}182Please respect copyright.ＰＥＮＡＮＡFlMyfpeNzb
return 2 * answer;182Please respect copyright.ＰＥＮＡＮＡPEV2UQKQTO
}182Please respect copyright.ＰＥＮＡＮＡMgO8cRHgd8
}
182Please respect copyright.ＰＥＮＡＮＡWx3norBf44
