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 {124Please respect copyright.ＰＥＮＡＮＡC4rJcP4wxn
public int longestPalindrome(String[] words) {124Please respect copyright.ＰＥＮＡＮＡHc5Ltb2auA
HashMap<String, Integer> count = new HashMap<String, Integer>();124Please respect copyright.ＰＥＮＡＮＡBy2LI7B8SK
// Count the number of occurrences of each word using a hashmap124Please respect copyright.ＰＥＮＡＮＡZMxub2UO0i
for (String word : words) {124Please respect copyright.ＰＥＮＡＮＡ3Lwo8SDEeV
Integer countOfTheWord = count.get(word);124Please respect copyright.ＰＥＮＡＮＡBLi1H92XIW
if (countOfTheWord == null) {124Please respect copyright.ＰＥＮＡＮＡdoWZexD4KR
count.put(word, 1);124Please respect copyright.ＰＥＮＡＮＡwYGtS25qaj
} else {124Please respect copyright.ＰＥＮＡＮＡn6Hnq84fB1
count.put(word, countOfTheWord + 1);124Please respect copyright.ＰＥＮＡＮＡmceW2wrmU9
}124Please respect copyright.ＰＥＮＡＮＡdQuNn59Xzm
}124Please respect copyright.ＰＥＮＡＮＡ2WUkT7wXln
// 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 word124Please respect copyright.ＰＥＮＡＮＡF9Sz6gGrE6
int answer = 0;124Please respect copyright.ＰＥＮＡＮＡQqAHJJhU1B
boolean central = false;124Please respect copyright.ＰＥＮＡＮＡmetVHdgthB
for (Map.Entry<String, Integer> entry : count.entrySet()) {124Please respect copyright.ＰＥＮＡＮＡ86gAdqbStO
String word = entry.getKey();124Please respect copyright.ＰＥＮＡＮＡBKaejm8W0H
int countOfTheWord = entry.getValue();124Please respect copyright.ＰＥＮＡＮＡhyv6B6Ms4Y
// if the word is a palindrome124Please respect copyright.ＰＥＮＡＮＡCSAKN9YpAh
if (word.charAt(0) == word.charAt(1)) {124Please respect copyright.ＰＥＮＡＮＡbLsqfGt3eh
if (countOfTheWord % 2 == 0) {124Please respect copyright.ＰＥＮＡＮＡ6pWCDvSuAP
answer += countOfTheWord;124Please respect copyright.ＰＥＮＡＮＡKzSBwm6XaI
} else {124Please respect copyright.ＰＥＮＡＮＡmB3OfWFF75
answer += countOfTheWord - 1;124Please respect copyright.ＰＥＮＡＮＡMQ3OOMhY3T
central = true;124Please respect copyright.ＰＥＮＡＮＡwWsHRAvuEB
}124Please respect copyright.ＰＥＮＡＮＡuKuK05naGg
// consider a pair of non-palindrome words such that one is the reverse of another124Please respect copyright.ＰＥＮＡＮＡTw810vCkua
} else if (word.charAt(0) < word.charAt(1)) {124Please respect copyright.ＰＥＮＡＮＡQYMjIpG4Ft
String reversedWord = "" + word.charAt(1) + word.charAt(0);124Please respect copyright.ＰＥＮＡＮＡPNr45PYlLG
if (count.containsKey(reversedWord)) {124Please respect copyright.ＰＥＮＡＮＡmVWGFa31lT
answer += 2 * Math.min(countOfTheWord, count.get(reversedWord));124Please respect copyright.ＰＥＮＡＮＡYn1hEI2iRC
}124Please respect copyright.ＰＥＮＡＮＡCUDwdkObQk
}124Please respect copyright.ＰＥＮＡＮＡV3jUGHtnqY
}124Please respect copyright.ＰＥＮＡＮＡOrRlO2y6OY
if (central) {124Please respect copyright.ＰＥＮＡＮＡkKLAPSSQm5
answer++;124Please respect copyright.ＰＥＮＡＮＡRLHMpZc1NY
}124Please respect copyright.ＰＥＮＡＮＡWzkQiVQzJn
return 2 * answer;124Please respect copyright.ＰＥＮＡＮＡ5qyYQ7sBgk
}124Please respect copyright.ＰＥＮＡＮＡCFImOMR0qr
}
2: A Two-Dimensional Array Approach
class Solution {124Please respect copyright.ＰＥＮＡＮＡrZGPQWenHM
public int longestPalindrome(String[] words) {124Please respect copyright.ＰＥＮＡＮＡVCrIVFhac0
final int alphabetSize = 26;124Please respect copyright.ＰＥＮＡＮＡiA47gVkLez
int[][] count = new int[alphabetSize][alphabetSize];124Please respect copyright.ＰＥＮＡＮＡ95lRal4zE9
// Count the number of occurrences of each word using a two-dimensional array. 124Please respect copyright.ＰＥＮＡＮＡBMEXLW8T80
for (String word : words) {124Please respect copyright.ＰＥＮＡＮＡ9sR5w1gJ2y
count[word.charAt(0) - 'a'][word.charAt(1) - 'a']++;124Please respect copyright.ＰＥＮＡＮＡl5HQHLfRkG
}124Please respect copyright.ＰＥＮＡＮＡVRAsC0J30R
// The answer will denote the number of words in the final string and the boolean variable central will denote whether we have a central word124Please respect copyright.ＰＥＮＡＮＡBnbr7diZON
int answer = 0;124Please respect copyright.ＰＥＮＡＮＡe0a0nyaSc0
boolean central = false;124Please respect copyright.ＰＥＮＡＮＡqouzkp9yUG
for (int i = 0; i < alphabetSize; i++) {124Please respect copyright.ＰＥＮＡＮＡFj3prXlLkB
if (count[i][i] % 2 == 0) {124Please respect copyright.ＰＥＮＡＮＡP5XywWKs2x
answer += count[i][i];124Please respect copyright.ＰＥＮＡＮＡcA34YOoB8e
} else {124Please respect copyright.ＰＥＮＡＮＡsSB6oULoZl
answer += count[i][i] - 1;124Please respect copyright.ＰＥＮＡＮＡIac5eV8fh4
central = true;124Please respect copyright.ＰＥＮＡＮＡFfhv0qLuWI
}124Please respect copyright.ＰＥＮＡＮＡK5VIeHz4UT
for (int j = i + 1; j < alphabetSize; j++) {124Please respect copyright.ＰＥＮＡＮＡSRQy0KfkLs
answer += 2 * Math.min(count[i][j], count[j][i]);124Please respect copyright.ＰＥＮＡＮＡfwlHujVHUP
}124Please respect copyright.ＰＥＮＡＮＡd5Q9BNkmBK
}124Please respect copyright.ＰＥＮＡＮＡtZZyqfFpcL
if (central) {124Please respect copyright.ＰＥＮＡＮＡF5TpuUhqOd
answer++;124Please respect copyright.ＰＥＮＡＮＡFivKRFR1uO
}124Please respect copyright.ＰＥＮＡＮＡWiJDSauQBh
return 2 * answer;124Please respect copyright.ＰＥＮＡＮＡVkjI2gJglm
}124Please respect copyright.ＰＥＮＡＮＡPGRLbz8q6f
}
124Please respect copyright.ＰＥＮＡＮＡhZFriHd891
