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 {195Please respect copyright.ＰＥＮＡＮＡWQci1rdS5c
public int longestPalindrome(String[] words) {195Please respect copyright.ＰＥＮＡＮＡLAkl8lqEp9
HashMap<String, Integer> count = new HashMap<String, Integer>();195Please respect copyright.ＰＥＮＡＮＡ4llz6L4A80
// Count the number of occurrences of each word using a hashmap195Please respect copyright.ＰＥＮＡＮＡ6qkcN0ZbjG
for (String word : words) {195Please respect copyright.ＰＥＮＡＮＡt3GyYouJwd
Integer countOfTheWord = count.get(word);195Please respect copyright.ＰＥＮＡＮＡhPNC5TGaU6
if (countOfTheWord == null) {195Please respect copyright.ＰＥＮＡＮＡVevljqSETa
count.put(word, 1);195Please respect copyright.ＰＥＮＡＮＡ56LJeLlE7J
} else {195Please respect copyright.ＰＥＮＡＮＡ6cNYceivdl
count.put(word, countOfTheWord + 1);195Please respect copyright.ＰＥＮＡＮＡUNZeYbTbid
}195Please respect copyright.ＰＥＮＡＮＡAxLG6301hA
}195Please respect copyright.ＰＥＮＡＮＡ15KoR1cXhX
// 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 word195Please respect copyright.ＰＥＮＡＮＡWf2Q9mlRwV
int answer = 0;195Please respect copyright.ＰＥＮＡＮＡSOqEb25wAh
boolean central = false;195Please respect copyright.ＰＥＮＡＮＡQc1gFT0Eqz
for (Map.Entry<String, Integer> entry : count.entrySet()) {195Please respect copyright.ＰＥＮＡＮＡBT5l5qlAWM
String word = entry.getKey();195Please respect copyright.ＰＥＮＡＮＡ5tj2VMQDpp
int countOfTheWord = entry.getValue();195Please respect copyright.ＰＥＮＡＮＡIvmhhgBhaR
// if the word is a palindrome195Please respect copyright.ＰＥＮＡＮＡkKyfO953zr
if (word.charAt(0) == word.charAt(1)) {195Please respect copyright.ＰＥＮＡＮＡCoNMvN5Hxy
if (countOfTheWord % 2 == 0) {195Please respect copyright.ＰＥＮＡＮＡObbCNFEFyC
answer += countOfTheWord;195Please respect copyright.ＰＥＮＡＮＡ0VombEMLEs
} else {195Please respect copyright.ＰＥＮＡＮＡYGShjHNcdK
answer += countOfTheWord - 1;195Please respect copyright.ＰＥＮＡＮＡocZ3byO9uS
central = true;195Please respect copyright.ＰＥＮＡＮＡdlx4ChPQxt
}195Please respect copyright.ＰＥＮＡＮＡBR062nDTIJ
// consider a pair of non-palindrome words such that one is the reverse of another195Please respect copyright.ＰＥＮＡＮＡ88iRHoyfUa
} else if (word.charAt(0) < word.charAt(1)) {195Please respect copyright.ＰＥＮＡＮＡbWC0tOjZSO
String reversedWord = "" + word.charAt(1) + word.charAt(0);195Please respect copyright.ＰＥＮＡＮＡbr42uLSaYZ
if (count.containsKey(reversedWord)) {195Please respect copyright.ＰＥＮＡＮＡVQ95R20G5m
answer += 2 * Math.min(countOfTheWord, count.get(reversedWord));195Please respect copyright.ＰＥＮＡＮＡakjT1645RD
}195Please respect copyright.ＰＥＮＡＮＡWuPlb2Pmmz
}195Please respect copyright.ＰＥＮＡＮＡCi5vXbMU8u
}195Please respect copyright.ＰＥＮＡＮＡMKX9vBz8ZE
if (central) {195Please respect copyright.ＰＥＮＡＮＡKLGgXvuRBv
answer++;195Please respect copyright.ＰＥＮＡＮＡXy0ekH245L
}195Please respect copyright.ＰＥＮＡＮＡlEFQ3Axn4z
return 2 * answer;195Please respect copyright.ＰＥＮＡＮＡqyrTnuYVoe
}195Please respect copyright.ＰＥＮＡＮＡ3kooI3qdoA
}
2: A Two-Dimensional Array Approach
class Solution {195Please respect copyright.ＰＥＮＡＮＡsqj6xxzVUN
public int longestPalindrome(String[] words) {195Please respect copyright.ＰＥＮＡＮＡvVJo5y6KBF
final int alphabetSize = 26;195Please respect copyright.ＰＥＮＡＮＡLU1ivrU0Vr
int[][] count = new int[alphabetSize][alphabetSize];195Please respect copyright.ＰＥＮＡＮＡWBgTwYPc3Q
// Count the number of occurrences of each word using a two-dimensional array. 195Please respect copyright.ＰＥＮＡＮＡoj3xabCORi
for (String word : words) {195Please respect copyright.ＰＥＮＡＮＡlNja3dhpDw
count[word.charAt(0) - 'a'][word.charAt(1) - 'a']++;195Please respect copyright.ＰＥＮＡＮＡrxzrml9CNm
}195Please respect copyright.ＰＥＮＡＮＡeTTMv1WR28
// The answer will denote the number of words in the final string and the boolean variable central will denote whether we have a central word195Please respect copyright.ＰＥＮＡＮＡaF3RBwmGPr
int answer = 0;195Please respect copyright.ＰＥＮＡＮＡO1wnK0mlvG
boolean central = false;195Please respect copyright.ＰＥＮＡＮＡpw8s1GBNBH
for (int i = 0; i < alphabetSize; i++) {195Please respect copyright.ＰＥＮＡＮＡq5yHEOWqei
if (count[i][i] % 2 == 0) {195Please respect copyright.ＰＥＮＡＮＡyiQqMwrt4g
answer += count[i][i];195Please respect copyright.ＰＥＮＡＮＡJGZ50oyho6
} else {195Please respect copyright.ＰＥＮＡＮＡA9xqMAEouK
answer += count[i][i] - 1;195Please respect copyright.ＰＥＮＡＮＡsnB2eYmyqN
central = true;195Please respect copyright.ＰＥＮＡＮＡdWmYbNKZdE
}195Please respect copyright.ＰＥＮＡＮＡlnD89SPj4s
for (int j = i + 1; j < alphabetSize; j++) {195Please respect copyright.ＰＥＮＡＮＡLcZWrABnYG
answer += 2 * Math.min(count[i][j], count[j][i]);195Please respect copyright.ＰＥＮＡＮＡPTmzuTFlOR
}195Please respect copyright.ＰＥＮＡＮＡo6qEpygdcf
}195Please respect copyright.ＰＥＮＡＮＡKRvfeeX7Vh
if (central) {195Please respect copyright.ＰＥＮＡＮＡTxxY1yWIQY
answer++;195Please respect copyright.ＰＥＮＡＮＡ32acKlCH8R
}195Please respect copyright.ＰＥＮＡＮＡgCB7x19gmw
return 2 * answer;195Please respect copyright.ＰＥＮＡＮＡKWnujTObf8
}195Please respect copyright.ＰＥＮＡＮＡ0R36M3rQCX
}
195Please respect copyright.ＰＥＮＡＮＡMKNie3Pje3
