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 {286Please respect copyright.ＰＥＮＡＮＡt60wu7gNYS
public int longestPalindrome(String[] words) {286Please respect copyright.ＰＥＮＡＮＡIIDBhq77mL
HashMap<String, Integer> count = new HashMap<String, Integer>();286Please respect copyright.ＰＥＮＡＮＡQfOzqbkzvi
// Count the number of occurrences of each word using a hashmap286Please respect copyright.ＰＥＮＡＮＡEuhM8spuQ7
for (String word : words) {286Please respect copyright.ＰＥＮＡＮＡM7hJJJNQDu
Integer countOfTheWord = count.get(word);286Please respect copyright.ＰＥＮＡＮＡ1mFoeW3fXr
if (countOfTheWord == null) {286Please respect copyright.ＰＥＮＡＮＡ1xSN3dqbpX
count.put(word, 1);286Please respect copyright.ＰＥＮＡＮＡR00J5xSWQG
} else {286Please respect copyright.ＰＥＮＡＮＡT6kvNXrd6z
count.put(word, countOfTheWord + 1);286Please respect copyright.ＰＥＮＡＮＡs75snp6Ykc
}286Please respect copyright.ＰＥＮＡＮＡLNYZo5adcP
}286Please respect copyright.ＰＥＮＡＮＡihTGPr8bXP
// 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 word286Please respect copyright.ＰＥＮＡＮＡ2oNuRggv6C
int answer = 0;286Please respect copyright.ＰＥＮＡＮＡxmfIFcAKWh
boolean central = false;286Please respect copyright.ＰＥＮＡＮＡsZVdpCtnq5
for (Map.Entry<String, Integer> entry : count.entrySet()) {286Please respect copyright.ＰＥＮＡＮＡJaxE6YgEn0
String word = entry.getKey();286Please respect copyright.ＰＥＮＡＮＡoxiF46Lr2n
int countOfTheWord = entry.getValue();286Please respect copyright.ＰＥＮＡＮＡSGp2bJ3Fli
// if the word is a palindrome286Please respect copyright.ＰＥＮＡＮＡ4qFZkq8kaw
if (word.charAt(0) == word.charAt(1)) {286Please respect copyright.ＰＥＮＡＮＡNKB5KVDXsV
if (countOfTheWord % 2 == 0) {286Please respect copyright.ＰＥＮＡＮＡP1xLdTIDqG
answer += countOfTheWord;286Please respect copyright.ＰＥＮＡＮＡPc5oPXLkMV
} else {286Please respect copyright.ＰＥＮＡＮＡTTp2MyaReR
answer += countOfTheWord - 1;286Please respect copyright.ＰＥＮＡＮＡpMj7nPTcyx
central = true;286Please respect copyright.ＰＥＮＡＮＡz0SsB6uTLb
}286Please respect copyright.ＰＥＮＡＮＡL3kgECwVMY
// consider a pair of non-palindrome words such that one is the reverse of another286Please respect copyright.ＰＥＮＡＮＡRa17hKmlAY
} else if (word.charAt(0) < word.charAt(1)) {286Please respect copyright.ＰＥＮＡＮＡ7QPL2B6JBD
String reversedWord = "" + word.charAt(1) + word.charAt(0);286Please respect copyright.ＰＥＮＡＮＡks8QmkL17A
if (count.containsKey(reversedWord)) {286Please respect copyright.ＰＥＮＡＮＡmBa5ir1GW3
answer += 2 * Math.min(countOfTheWord, count.get(reversedWord));286Please respect copyright.ＰＥＮＡＮＡeJhCZcvjUA
}286Please respect copyright.ＰＥＮＡＮＡbEL1pzLdYh
}286Please respect copyright.ＰＥＮＡＮＡqO9pSugfTK
}286Please respect copyright.ＰＥＮＡＮＡMoNjVOGBU8
if (central) {286Please respect copyright.ＰＥＮＡＮＡd5my2srj1I
answer++;286Please respect copyright.ＰＥＮＡＮＡEOJyFK7Afo
}286Please respect copyright.ＰＥＮＡＮＡY9W4EwZQtd
return 2 * answer;286Please respect copyright.ＰＥＮＡＮＡrfD55PFURM
}286Please respect copyright.ＰＥＮＡＮＡPObe0LXWUV
}
2: A Two-Dimensional Array Approach
class Solution {286Please respect copyright.ＰＥＮＡＮＡWEdiXMZd9v
public int longestPalindrome(String[] words) {286Please respect copyright.ＰＥＮＡＮＡ5klHe2wHj2
final int alphabetSize = 26;286Please respect copyright.ＰＥＮＡＮＡj6OOGPoYNt
int[][] count = new int[alphabetSize][alphabetSize];286Please respect copyright.ＰＥＮＡＮＡ3ec9Z7Sre4
// Count the number of occurrences of each word using a two-dimensional array. 286Please respect copyright.ＰＥＮＡＮＡJc05hER67S
for (String word : words) {286Please respect copyright.ＰＥＮＡＮＡsm7jiPF8E7
count[word.charAt(0) - 'a'][word.charAt(1) - 'a']++;286Please respect copyright.ＰＥＮＡＮＡlzYt1cmYPU
}286Please respect copyright.ＰＥＮＡＮＡRxoBDSdxBa
// The answer will denote the number of words in the final string and the boolean variable central will denote whether we have a central word286Please respect copyright.ＰＥＮＡＮＡj2yh5iC7Wx
int answer = 0;286Please respect copyright.ＰＥＮＡＮＡg9paVCQQ9I
boolean central = false;286Please respect copyright.ＰＥＮＡＮＡKOmD6LY1Mc
for (int i = 0; i < alphabetSize; i++) {286Please respect copyright.ＰＥＮＡＮＡRFWyulqEyG
if (count[i][i] % 2 == 0) {286Please respect copyright.ＰＥＮＡＮＡw6JLWvQNv0
answer += count[i][i];286Please respect copyright.ＰＥＮＡＮＡguUPLI0JJf
} else {286Please respect copyright.ＰＥＮＡＮＡRnjcABmyn5
answer += count[i][i] - 1;286Please respect copyright.ＰＥＮＡＮＡIXRbKIYr0s
central = true;286Please respect copyright.ＰＥＮＡＮＡyaDNLjsrWb
}286Please respect copyright.ＰＥＮＡＮＡNHUMmwWPiE
for (int j = i + 1; j < alphabetSize; j++) {286Please respect copyright.ＰＥＮＡＮＡL1Es4H0Ymq
answer += 2 * Math.min(count[i][j], count[j][i]);286Please respect copyright.ＰＥＮＡＮＡgg9eBOm8J8
}286Please respect copyright.ＰＥＮＡＮＡbbjgpqZ2R1
}286Please respect copyright.ＰＥＮＡＮＡPyu4yO41ua
if (central) {286Please respect copyright.ＰＥＮＡＮＡZZOhXClkiE
answer++;286Please respect copyright.ＰＥＮＡＮＡ12Ctj0vPP3
}286Please respect copyright.ＰＥＮＡＮＡiTwqwF2Ef9
return 2 * answer;286Please respect copyright.ＰＥＮＡＮＡ6OaHXEFjTW
}286Please respect copyright.ＰＥＮＡＮＡ0faeUcGARG
}
286Please respect copyright.ＰＥＮＡＮＡTD73bW6ojs
