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 {242Please respect copyright.ＰＥＮＡＮＡufPw1vmPMR
public int longestPalindrome(String[] words) {242Please respect copyright.ＰＥＮＡＮＡMzgu2nhPgX
HashMap<String, Integer> count = new HashMap<String, Integer>();242Please respect copyright.ＰＥＮＡＮＡW3uApG0EaE
// Count the number of occurrences of each word using a hashmap242Please respect copyright.ＰＥＮＡＮＡY8zLj2KoMQ
for (String word : words) {242Please respect copyright.ＰＥＮＡＮＡNb0GogO7sj
Integer countOfTheWord = count.get(word);242Please respect copyright.ＰＥＮＡＮＡtfFwGM3mW5
if (countOfTheWord == null) {242Please respect copyright.ＰＥＮＡＮＡkfNxUwkqGz
count.put(word, 1);242Please respect copyright.ＰＥＮＡＮＡgSsb0ZFkxy
} else {242Please respect copyright.ＰＥＮＡＮＡCbEoJC5NRr
count.put(word, countOfTheWord + 1);242Please respect copyright.ＰＥＮＡＮＡ43bPSla3Xz
}242Please respect copyright.ＰＥＮＡＮＡSEjvtlpCEI
}242Please respect copyright.ＰＥＮＡＮＡKrLMbZUu4I
// 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 word242Please respect copyright.ＰＥＮＡＮＡCJE0UWgeTz
int answer = 0;242Please respect copyright.ＰＥＮＡＮＡCxslx6D0qH
boolean central = false;242Please respect copyright.ＰＥＮＡＮＡ9g7ja9tShn
for (Map.Entry<String, Integer> entry : count.entrySet()) {242Please respect copyright.ＰＥＮＡＮＡkwrax5OpV3
String word = entry.getKey();242Please respect copyright.ＰＥＮＡＮＡfiqzeeoExq
int countOfTheWord = entry.getValue();242Please respect copyright.ＰＥＮＡＮＡufV6bXxMxw
// if the word is a palindrome242Please respect copyright.ＰＥＮＡＮＡzINl9NVxRE
if (word.charAt(0) == word.charAt(1)) {242Please respect copyright.ＰＥＮＡＮＡtbVHU2BQqh
if (countOfTheWord % 2 == 0) {242Please respect copyright.ＰＥＮＡＮＡIPhpf2wlnk
answer += countOfTheWord;242Please respect copyright.ＰＥＮＡＮＡdM5SYMIPiy
} else {242Please respect copyright.ＰＥＮＡＮＡJjDSWtLLDO
answer += countOfTheWord - 1;242Please respect copyright.ＰＥＮＡＮＡP96kcJq0KP
central = true;242Please respect copyright.ＰＥＮＡＮＡnXoUTstBw2
}242Please respect copyright.ＰＥＮＡＮＡJCv7bVbDLJ
// consider a pair of non-palindrome words such that one is the reverse of another242Please respect copyright.ＰＥＮＡＮＡBqH1Uijb3B
} else if (word.charAt(0) < word.charAt(1)) {242Please respect copyright.ＰＥＮＡＮＡk0WiFQ6CzO
String reversedWord = "" + word.charAt(1) + word.charAt(0);242Please respect copyright.ＰＥＮＡＮＡmm73cBgYdL
if (count.containsKey(reversedWord)) {242Please respect copyright.ＰＥＮＡＮＡK1DztdSf1R
answer += 2 * Math.min(countOfTheWord, count.get(reversedWord));242Please respect copyright.ＰＥＮＡＮＡozPb5hvJ6K
}242Please respect copyright.ＰＥＮＡＮＡBrU3LWjlIu
}242Please respect copyright.ＰＥＮＡＮＡhU2xYPn4td
}242Please respect copyright.ＰＥＮＡＮＡRG4q8VatPt
if (central) {242Please respect copyright.ＰＥＮＡＮＡ4NAlaL0BDA
answer++;242Please respect copyright.ＰＥＮＡＮＡGXnSq0txqe
}242Please respect copyright.ＰＥＮＡＮＡD0DuFpVA6f
return 2 * answer;242Please respect copyright.ＰＥＮＡＮＡEZSuv6thuY
}242Please respect copyright.ＰＥＮＡＮＡ2TmGdXco0r
}
2: A Two-Dimensional Array Approach
class Solution {242Please respect copyright.ＰＥＮＡＮＡQ4SaVBLnX8
public int longestPalindrome(String[] words) {242Please respect copyright.ＰＥＮＡＮＡTrU6cEu5FU
final int alphabetSize = 26;242Please respect copyright.ＰＥＮＡＮＡ3yK6jsIugQ
int[][] count = new int[alphabetSize][alphabetSize];242Please respect copyright.ＰＥＮＡＮＡ66MJTjdxnF
// Count the number of occurrences of each word using a two-dimensional array. 242Please respect copyright.ＰＥＮＡＮＡSkWJlSoe3R
for (String word : words) {242Please respect copyright.ＰＥＮＡＮＡU6jiiY3NGj
count[word.charAt(0) - 'a'][word.charAt(1) - 'a']++;242Please respect copyright.ＰＥＮＡＮＡVS3kbGzzuy
}242Please respect copyright.ＰＥＮＡＮＡ1URzLXp8vz
// The answer will denote the number of words in the final string and the boolean variable central will denote whether we have a central word242Please respect copyright.ＰＥＮＡＮＡazToEyg8HL
int answer = 0;242Please respect copyright.ＰＥＮＡＮＡWq6ec6xKp1
boolean central = false;242Please respect copyright.ＰＥＮＡＮＡNQRokZUCBK
for (int i = 0; i < alphabetSize; i++) {242Please respect copyright.ＰＥＮＡＮＡc8a5AiedNW
if (count[i][i] % 2 == 0) {242Please respect copyright.ＰＥＮＡＮＡDkpRnJsLLP
answer += count[i][i];242Please respect copyright.ＰＥＮＡＮＡ8Iuzotn6b7
} else {242Please respect copyright.ＰＥＮＡＮＡ7M2FxP8pOQ
answer += count[i][i] - 1;242Please respect copyright.ＰＥＮＡＮＡVLAhj5fNUp
central = true;242Please respect copyright.ＰＥＮＡＮＡNfgRdGgqkP
}242Please respect copyright.ＰＥＮＡＮＡvN4RzNU91S
for (int j = i + 1; j < alphabetSize; j++) {242Please respect copyright.ＰＥＮＡＮＡePaRA4KuTC
answer += 2 * Math.min(count[i][j], count[j][i]);242Please respect copyright.ＰＥＮＡＮＡKnU71UEMP7
}242Please respect copyright.ＰＥＮＡＮＡflBLZQlp93
}242Please respect copyright.ＰＥＮＡＮＡkZSfuF2nbo
if (central) {242Please respect copyright.ＰＥＮＡＮＡCrqOIyAVVM
answer++;242Please respect copyright.ＰＥＮＡＮＡTYkZktsPPY
}242Please respect copyright.ＰＥＮＡＮＡ4gqPZ2GCs5
return 2 * answer;242Please respect copyright.ＰＥＮＡＮＡKpPLf9xZMr
}242Please respect copyright.ＰＥＮＡＮＡh6nFUFVEBm
}
242Please respect copyright.ＰＥＮＡＮＡLjVBVK9rd6
