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 {258Please respect copyright.ＰＥＮＡＮＡ6BF6V2pwd6
public int longestPalindrome(String[] words) {258Please respect copyright.ＰＥＮＡＮＡovl4iL3tyx
HashMap<String, Integer> count = new HashMap<String, Integer>();258Please respect copyright.ＰＥＮＡＮＡlCjePrxV0r
// Count the number of occurrences of each word using a hashmap258Please respect copyright.ＰＥＮＡＮＡSC65g17cc6
for (String word : words) {258Please respect copyright.ＰＥＮＡＮＡ2j2stL0QgZ
Integer countOfTheWord = count.get(word);258Please respect copyright.ＰＥＮＡＮＡLidHfK8JyF
if (countOfTheWord == null) {258Please respect copyright.ＰＥＮＡＮＡMrjYf5G27r
count.put(word, 1);258Please respect copyright.ＰＥＮＡＮＡyeiSAv90aw
} else {258Please respect copyright.ＰＥＮＡＮＡMn5BHoqh83
count.put(word, countOfTheWord + 1);258Please respect copyright.ＰＥＮＡＮＡsrWC4d3raf
}258Please respect copyright.ＰＥＮＡＮＡbP5eSDA2rq
}258Please respect copyright.ＰＥＮＡＮＡfbmGyzW5kx
// 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 word258Please respect copyright.ＰＥＮＡＮＡeP3SSmDVBq
int answer = 0;258Please respect copyright.ＰＥＮＡＮＡHXWXPSELGE
boolean central = false;258Please respect copyright.ＰＥＮＡＮＡkB9UoGCSi4
for (Map.Entry<String, Integer> entry : count.entrySet()) {258Please respect copyright.ＰＥＮＡＮＡrFLAeTeQFS
String word = entry.getKey();258Please respect copyright.ＰＥＮＡＮＡ17SLsioiig
int countOfTheWord = entry.getValue();258Please respect copyright.ＰＥＮＡＮＡdZ331BO7zL
// if the word is a palindrome258Please respect copyright.ＰＥＮＡＮＡGlOhEqVGjc
if (word.charAt(0) == word.charAt(1)) {258Please respect copyright.ＰＥＮＡＮＡ5g2kXQUzH1
if (countOfTheWord % 2 == 0) {258Please respect copyright.ＰＥＮＡＮＡVOrYG7eZp7
answer += countOfTheWord;258Please respect copyright.ＰＥＮＡＮＡiiPtx584Yt
} else {258Please respect copyright.ＰＥＮＡＮＡbAKXIZSqBU
answer += countOfTheWord - 1;258Please respect copyright.ＰＥＮＡＮＡayTWACU56h
central = true;258Please respect copyright.ＰＥＮＡＮＡj5oA1sZCiI
}258Please respect copyright.ＰＥＮＡＮＡ0MKPH4W5yb
// consider a pair of non-palindrome words such that one is the reverse of another258Please respect copyright.ＰＥＮＡＮＡ5XGAYF8vve
} else if (word.charAt(0) < word.charAt(1)) {258Please respect copyright.ＰＥＮＡＮＡmQSJRFSYcb
String reversedWord = "" + word.charAt(1) + word.charAt(0);258Please respect copyright.ＰＥＮＡＮＡixN7nJCpwf
if (count.containsKey(reversedWord)) {258Please respect copyright.ＰＥＮＡＮＡT0GCCvI1Fv
answer += 2 * Math.min(countOfTheWord, count.get(reversedWord));258Please respect copyright.ＰＥＮＡＮＡQuV2fYfzPT
}258Please respect copyright.ＰＥＮＡＮＡLcbhJb4kLV
}258Please respect copyright.ＰＥＮＡＮＡu9QxfCWSMq
}258Please respect copyright.ＰＥＮＡＮＡDyALlbtbHj
if (central) {258Please respect copyright.ＰＥＮＡＮＡbseppY7jyE
answer++;258Please respect copyright.ＰＥＮＡＮＡFIfjMyYSie
}258Please respect copyright.ＰＥＮＡＮＡiChyoxhJkY
return 2 * answer;258Please respect copyright.ＰＥＮＡＮＡPsNpVz0sP1
}258Please respect copyright.ＰＥＮＡＮＡBqflMDDfti
}
2: A Two-Dimensional Array Approach
class Solution {258Please respect copyright.ＰＥＮＡＮＡ3zR5LC67x5
public int longestPalindrome(String[] words) {258Please respect copyright.ＰＥＮＡＮＡDDuFheVRgz
final int alphabetSize = 26;258Please respect copyright.ＰＥＮＡＮＡKvDcQMtnU0
int[][] count = new int[alphabetSize][alphabetSize];258Please respect copyright.ＰＥＮＡＮＡ2FGYSOnyjz
// Count the number of occurrences of each word using a two-dimensional array. 258Please respect copyright.ＰＥＮＡＮＡRYYUSqWxAM
for (String word : words) {258Please respect copyright.ＰＥＮＡＮＡZS6s7yM4jr
count[word.charAt(0) - 'a'][word.charAt(1) - 'a']++;258Please respect copyright.ＰＥＮＡＮＡy5X5VjjMSk
}258Please respect copyright.ＰＥＮＡＮＡ9J50zWpj1y
// The answer will denote the number of words in the final string and the boolean variable central will denote whether we have a central word258Please respect copyright.ＰＥＮＡＮＡ5JLfLl4UQn
int answer = 0;258Please respect copyright.ＰＥＮＡＮＡb0Lv3NXnoe
boolean central = false;258Please respect copyright.ＰＥＮＡＮＡD6zPYnvpma
for (int i = 0; i < alphabetSize; i++) {258Please respect copyright.ＰＥＮＡＮＡE9TCjZyYgl
if (count[i][i] % 2 == 0) {258Please respect copyright.ＰＥＮＡＮＡILxhbikVeW
answer += count[i][i];258Please respect copyright.ＰＥＮＡＮＡTzUbwUiHdF
} else {258Please respect copyright.ＰＥＮＡＮＡo1XSzJKbEB
answer += count[i][i] - 1;258Please respect copyright.ＰＥＮＡＮＡLSxesdpHeI
central = true;258Please respect copyright.ＰＥＮＡＮＡRfiNZdQpLf
}258Please respect copyright.ＰＥＮＡＮＡgob0V2OJMr
for (int j = i + 1; j < alphabetSize; j++) {258Please respect copyright.ＰＥＮＡＮＡGn1Jj6ygDx
answer += 2 * Math.min(count[i][j], count[j][i]);258Please respect copyright.ＰＥＮＡＮＡ7XSSR3pdpn
}258Please respect copyright.ＰＥＮＡＮＡjRc1jTLw2x
}258Please respect copyright.ＰＥＮＡＮＡ6ZpxdqmdRD
if (central) {258Please respect copyright.ＰＥＮＡＮＡE1NWeWQsMZ
answer++;258Please respect copyright.ＰＥＮＡＮＡKR8bskKsSc
}258Please respect copyright.ＰＥＮＡＮＡprGLZIDXlq
return 2 * answer;258Please respect copyright.ＰＥＮＡＮＡ1WA3dn2FbY
}258Please respect copyright.ＰＥＮＡＮＡUYYasMAvcC
}
258Please respect copyright.ＰＥＮＡＮＡhCrPuSwWYm
