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 {232Please respect copyright.ＰＥＮＡＮＡdaA24B0Abt
public int longestPalindrome(String[] words) {232Please respect copyright.ＰＥＮＡＮＡH1Tob86Kyz
HashMap<String, Integer> count = new HashMap<String, Integer>();232Please respect copyright.ＰＥＮＡＮＡAVJzActCNY
// Count the number of occurrences of each word using a hashmap232Please respect copyright.ＰＥＮＡＮＡtXsUXOwxPH
for (String word : words) {232Please respect copyright.ＰＥＮＡＮＡsXGUPZR5uJ
Integer countOfTheWord = count.get(word);232Please respect copyright.ＰＥＮＡＮＡU8u0cYZSuL
if (countOfTheWord == null) {232Please respect copyright.ＰＥＮＡＮＡYSA2qsMw70
count.put(word, 1);232Please respect copyright.ＰＥＮＡＮＡQdJPnvcloK
} else {232Please respect copyright.ＰＥＮＡＮＡ3kukYCmP7i
count.put(word, countOfTheWord + 1);232Please respect copyright.ＰＥＮＡＮＡk6il7aLq0k
}232Please respect copyright.ＰＥＮＡＮＡN5ieREbsTn
}232Please respect copyright.ＰＥＮＡＮＡoP649GPhzM
// 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 word232Please respect copyright.ＰＥＮＡＮＡWFJCdpY6jv
int answer = 0;232Please respect copyright.ＰＥＮＡＮＡep8PVzJ9iI
boolean central = false;232Please respect copyright.ＰＥＮＡＮＡ0cni8pRkI4
for (Map.Entry<String, Integer> entry : count.entrySet()) {232Please respect copyright.ＰＥＮＡＮＡufGaiwcVBL
String word = entry.getKey();232Please respect copyright.ＰＥＮＡＮＡqd3ncRbjNq
int countOfTheWord = entry.getValue();232Please respect copyright.ＰＥＮＡＮＡW6VnXmFVUI
// if the word is a palindrome232Please respect copyright.ＰＥＮＡＮＡuunlKktUjR
if (word.charAt(0) == word.charAt(1)) {232Please respect copyright.ＰＥＮＡＮＡUeHGJCHlDk
if (countOfTheWord % 2 == 0) {232Please respect copyright.ＰＥＮＡＮＡ9h8IcV5FMe
answer += countOfTheWord;232Please respect copyright.ＰＥＮＡＮＡq6FgILMF3u
} else {232Please respect copyright.ＰＥＮＡＮＡzy577AaOAe
answer += countOfTheWord - 1;232Please respect copyright.ＰＥＮＡＮＡOk6ICOIblT
central = true;232Please respect copyright.ＰＥＮＡＮＡk6lpsugUJM
}232Please respect copyright.ＰＥＮＡＮＡAuEaFPG8AX
// consider a pair of non-palindrome words such that one is the reverse of another232Please respect copyright.ＰＥＮＡＮＡZrIDNVnB2P
} else if (word.charAt(0) < word.charAt(1)) {232Please respect copyright.ＰＥＮＡＮＡVHApF8LtqS
String reversedWord = "" + word.charAt(1) + word.charAt(0);232Please respect copyright.ＰＥＮＡＮＡHiwrRuwOrI
if (count.containsKey(reversedWord)) {232Please respect copyright.ＰＥＮＡＮＡHSQ2iaf7NM
answer += 2 * Math.min(countOfTheWord, count.get(reversedWord));232Please respect copyright.ＰＥＮＡＮＡYdlUTrFrRz
}232Please respect copyright.ＰＥＮＡＮＡYVuSyUZexB
}232Please respect copyright.ＰＥＮＡＮＡHySciWDsLR
}232Please respect copyright.ＰＥＮＡＮＡPMIcthNudI
if (central) {232Please respect copyright.ＰＥＮＡＮＡaVFSK1VmtO
answer++;232Please respect copyright.ＰＥＮＡＮＡdiWdI7PvMr
}232Please respect copyright.ＰＥＮＡＮＡdYIwBep9VT
return 2 * answer;232Please respect copyright.ＰＥＮＡＮＡyrgcAtOtnF
}232Please respect copyright.ＰＥＮＡＮＡFVvTVXjuiZ
}
2: A Two-Dimensional Array Approach
class Solution {232Please respect copyright.ＰＥＮＡＮＡ5eG7obzBr3
public int longestPalindrome(String[] words) {232Please respect copyright.ＰＥＮＡＮＡn97hiSxNMj
final int alphabetSize = 26;232Please respect copyright.ＰＥＮＡＮＡVJA0wrR7J6
int[][] count = new int[alphabetSize][alphabetSize];232Please respect copyright.ＰＥＮＡＮＡW26OBPKeyw
// Count the number of occurrences of each word using a two-dimensional array. 232Please respect copyright.ＰＥＮＡＮＡhFryjotYxA
for (String word : words) {232Please respect copyright.ＰＥＮＡＮＡUQCPn6330K
count[word.charAt(0) - 'a'][word.charAt(1) - 'a']++;232Please respect copyright.ＰＥＮＡＮＡdPwEA24F7C
}232Please respect copyright.ＰＥＮＡＮＡKloiX7A6ea
// The answer will denote the number of words in the final string and the boolean variable central will denote whether we have a central word232Please respect copyright.ＰＥＮＡＮＡlfmR2K6pM9
int answer = 0;232Please respect copyright.ＰＥＮＡＮＡ7P5el42BTl
boolean central = false;232Please respect copyright.ＰＥＮＡＮＡkL6JmSClII
for (int i = 0; i < alphabetSize; i++) {232Please respect copyright.ＰＥＮＡＮＡHU05HO0gZK
if (count[i][i] % 2 == 0) {232Please respect copyright.ＰＥＮＡＮＡcN1OPDsisX
answer += count[i][i];232Please respect copyright.ＰＥＮＡＮＡ2V5pLmnEAS
} else {232Please respect copyright.ＰＥＮＡＮＡBD5eTqIdOJ
answer += count[i][i] - 1;232Please respect copyright.ＰＥＮＡＮＡxPA2bdkC5f
central = true;232Please respect copyright.ＰＥＮＡＮＡsJPTsCS9IM
}232Please respect copyright.ＰＥＮＡＮＡfBYvzp9IPi
for (int j = i + 1; j < alphabetSize; j++) {232Please respect copyright.ＰＥＮＡＮＡPor5zRZ8iR
answer += 2 * Math.min(count[i][j], count[j][i]);232Please respect copyright.ＰＥＮＡＮＡdt0ur2RdvW
}232Please respect copyright.ＰＥＮＡＮＡvYRdgKLA9y
}232Please respect copyright.ＰＥＮＡＮＡVLKfxR3AbW
if (central) {232Please respect copyright.ＰＥＮＡＮＡpo9sxu5DCt
answer++;232Please respect copyright.ＰＥＮＡＮＡTJ7bp9jxPd
}232Please respect copyright.ＰＥＮＡＮＡEDDzhD8RYy
return 2 * answer;232Please respect copyright.ＰＥＮＡＮＡAW0aDwNOQ4
}232Please respect copyright.ＰＥＮＡＮＡgn638WF4ZG
}
232Please respect copyright.ＰＥＮＡＮＡK4OOgKhzpN
