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 {229Please respect copyright.ＰＥＮＡＮＡoOsNnDDYPe
public int longestPalindrome(String[] words) {229Please respect copyright.ＰＥＮＡＮＡhTYyMrRfLH
HashMap<String, Integer> count = new HashMap<String, Integer>();229Please respect copyright.ＰＥＮＡＮＡ8JJyrd6ss4
// Count the number of occurrences of each word using a hashmap229Please respect copyright.ＰＥＮＡＮＡCnZCNde4BA
for (String word : words) {229Please respect copyright.ＰＥＮＡＮＡOQB28VJ45b
Integer countOfTheWord = count.get(word);229Please respect copyright.ＰＥＮＡＮＡBQ0qpIgqdP
if (countOfTheWord == null) {229Please respect copyright.ＰＥＮＡＮＡCwzt4qmuZV
count.put(word, 1);229Please respect copyright.ＰＥＮＡＮＡhaynziiJb0
} else {229Please respect copyright.ＰＥＮＡＮＡ39GVuJjNdc
count.put(word, countOfTheWord + 1);229Please respect copyright.ＰＥＮＡＮＡBzBYRimk6x
}229Please respect copyright.ＰＥＮＡＮＡ0Hh2d5XngJ
}229Please respect copyright.ＰＥＮＡＮＡs7yuTyrRtB
// 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 word229Please respect copyright.ＰＥＮＡＮＡKlDY7dE57v
int answer = 0;229Please respect copyright.ＰＥＮＡＮＡRz7AJO8eyH
boolean central = false;229Please respect copyright.ＰＥＮＡＮＡwYlKjGWWYG
for (Map.Entry<String, Integer> entry : count.entrySet()) {229Please respect copyright.ＰＥＮＡＮＡ952E6kPgTt
String word = entry.getKey();229Please respect copyright.ＰＥＮＡＮＡg3tVO7kiRD
int countOfTheWord = entry.getValue();229Please respect copyright.ＰＥＮＡＮＡgIby6oK8lw
// if the word is a palindrome229Please respect copyright.ＰＥＮＡＮＡT10PPNXkEh
if (word.charAt(0) == word.charAt(1)) {229Please respect copyright.ＰＥＮＡＮＡ0oicPpGY2v
if (countOfTheWord % 2 == 0) {229Please respect copyright.ＰＥＮＡＮＡBH5CBUM9fK
answer += countOfTheWord;229Please respect copyright.ＰＥＮＡＮＡy13i69p0b2
} else {229Please respect copyright.ＰＥＮＡＮＡdutUwizzCo
answer += countOfTheWord - 1;229Please respect copyright.ＰＥＮＡＮＡGDcpxhlBPF
central = true;229Please respect copyright.ＰＥＮＡＮＡ2UbQLR49rh
}229Please respect copyright.ＰＥＮＡＮＡ8FUxHg7AXb
// consider a pair of non-palindrome words such that one is the reverse of another229Please respect copyright.ＰＥＮＡＮＡKl6aw7jeu4
} else if (word.charAt(0) < word.charAt(1)) {229Please respect copyright.ＰＥＮＡＮＡYNWyRa8mbA
String reversedWord = "" + word.charAt(1) + word.charAt(0);229Please respect copyright.ＰＥＮＡＮＡ4ou7u3vHF8
if (count.containsKey(reversedWord)) {229Please respect copyright.ＰＥＮＡＮＡgjufqeNZw1
answer += 2 * Math.min(countOfTheWord, count.get(reversedWord));229Please respect copyright.ＰＥＮＡＮＡ7wvSFglqk0
}229Please respect copyright.ＰＥＮＡＮＡkkShfY4h96
}229Please respect copyright.ＰＥＮＡＮＡHJ7m6E78hS
}229Please respect copyright.ＰＥＮＡＮＡ9Od1KAzVZk
if (central) {229Please respect copyright.ＰＥＮＡＮＡN9SUnXRCMQ
answer++;229Please respect copyright.ＰＥＮＡＮＡcJKjX7Gj3S
}229Please respect copyright.ＰＥＮＡＮＡhkT4AANLpJ
return 2 * answer;229Please respect copyright.ＰＥＮＡＮＡ5YeD4s1JQu
}229Please respect copyright.ＰＥＮＡＮＡrqU18mOcOz
}
2: A Two-Dimensional Array Approach
class Solution {229Please respect copyright.ＰＥＮＡＮＡFjsVyqGYn3
public int longestPalindrome(String[] words) {229Please respect copyright.ＰＥＮＡＮＡtgnmYOg2GX
final int alphabetSize = 26;229Please respect copyright.ＰＥＮＡＮＡSuwDf5g0cO
int[][] count = new int[alphabetSize][alphabetSize];229Please respect copyright.ＰＥＮＡＮＡNsJVJHqZeu
// Count the number of occurrences of each word using a two-dimensional array. 229Please respect copyright.ＰＥＮＡＮＡhazA08CAqF
for (String word : words) {229Please respect copyright.ＰＥＮＡＮＡT6B6BUslyL
count[word.charAt(0) - 'a'][word.charAt(1) - 'a']++;229Please respect copyright.ＰＥＮＡＮＡ84J4Aw9eZi
}229Please respect copyright.ＰＥＮＡＮＡoNy3HXmHQe
// The answer will denote the number of words in the final string and the boolean variable central will denote whether we have a central word229Please respect copyright.ＰＥＮＡＮＡDaJFUOqoKT
int answer = 0;229Please respect copyright.ＰＥＮＡＮＡoKYEMfLfPc
boolean central = false;229Please respect copyright.ＰＥＮＡＮＡtcApkQXzKn
for (int i = 0; i < alphabetSize; i++) {229Please respect copyright.ＰＥＮＡＮＡVw8qUnIXEo
if (count[i][i] % 2 == 0) {229Please respect copyright.ＰＥＮＡＮＡAJDp8sfWlt
answer += count[i][i];229Please respect copyright.ＰＥＮＡＮＡlEradKNcHt
} else {229Please respect copyright.ＰＥＮＡＮＡxgfRpCG7mv
answer += count[i][i] - 1;229Please respect copyright.ＰＥＮＡＮＡbk8k3L0sPT
central = true;229Please respect copyright.ＰＥＮＡＮＡgtFD2wXS73
}229Please respect copyright.ＰＥＮＡＮＡNRLy8goTUJ
for (int j = i + 1; j < alphabetSize; j++) {229Please respect copyright.ＰＥＮＡＮＡm6pVZebAUn
answer += 2 * Math.min(count[i][j], count[j][i]);229Please respect copyright.ＰＥＮＡＮＡ7BnDIueGIO
}229Please respect copyright.ＰＥＮＡＮＡvchyacjPFR
}229Please respect copyright.ＰＥＮＡＮＡ3PctsxMEZI
if (central) {229Please respect copyright.ＰＥＮＡＮＡI3IOuAVbs6
answer++;229Please respect copyright.ＰＥＮＡＮＡiseFGlLB8U
}229Please respect copyright.ＰＥＮＡＮＡ119xnFO3qk
return 2 * answer;229Please respect copyright.ＰＥＮＡＮＡCUD14ATY6N
}229Please respect copyright.ＰＥＮＡＮＡhust5FbGoG
}
229Please respect copyright.ＰＥＮＡＮＡKbIr5PX8jw
