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 {212Please respect copyright.ＰＥＮＡＮＡPpsBfwjatJ
public int longestPalindrome(String[] words) {212Please respect copyright.ＰＥＮＡＮＡnkTFAKoKoF
HashMap<String, Integer> count = new HashMap<String, Integer>();212Please respect copyright.ＰＥＮＡＮＡ1kYUI5HgW7
// Count the number of occurrences of each word using a hashmap212Please respect copyright.ＰＥＮＡＮＡc1eSFpTlYW
for (String word : words) {212Please respect copyright.ＰＥＮＡＮＡ1u47bIRjIa
Integer countOfTheWord = count.get(word);212Please respect copyright.ＰＥＮＡＮＡwW4ADUJZGX
if (countOfTheWord == null) {212Please respect copyright.ＰＥＮＡＮＡK3VWogL5uz
count.put(word, 1);212Please respect copyright.ＰＥＮＡＮＡ26gsuzxUwI
} else {212Please respect copyright.ＰＥＮＡＮＡf49gVtcGVG
count.put(word, countOfTheWord + 1);212Please respect copyright.ＰＥＮＡＮＡZjnep79Vcj
}212Please respect copyright.ＰＥＮＡＮＡnTqzFpolgK
}212Please respect copyright.ＰＥＮＡＮＡnUHJSKqced
// 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 word212Please respect copyright.ＰＥＮＡＮＡ35Jo17K0Ol
int answer = 0;212Please respect copyright.ＰＥＮＡＮＡ2VyywNxN5Y
boolean central = false;212Please respect copyright.ＰＥＮＡＮＡgVEMEOEgoE
for (Map.Entry<String, Integer> entry : count.entrySet()) {212Please respect copyright.ＰＥＮＡＮＡ04mDZLYhUB
String word = entry.getKey();212Please respect copyright.ＰＥＮＡＮＡkZfeVoRRTF
int countOfTheWord = entry.getValue();212Please respect copyright.ＰＥＮＡＮＡ9aLDGmFO5w
// if the word is a palindrome212Please respect copyright.ＰＥＮＡＮＡogyjqWbQLc
if (word.charAt(0) == word.charAt(1)) {212Please respect copyright.ＰＥＮＡＮＡsdV9wIwmAP
if (countOfTheWord % 2 == 0) {212Please respect copyright.ＰＥＮＡＮＡC6CkZ1PUmN
answer += countOfTheWord;212Please respect copyright.ＰＥＮＡＮＡYkOx3HUVvK
} else {212Please respect copyright.ＰＥＮＡＮＡm8Mkkumhwy
answer += countOfTheWord - 1;212Please respect copyright.ＰＥＮＡＮＡObEiZdJSqG
central = true;212Please respect copyright.ＰＥＮＡＮＡJ1H34pBMyi
}212Please respect copyright.ＰＥＮＡＮＡbZMjE7QzAA
// consider a pair of non-palindrome words such that one is the reverse of another212Please respect copyright.ＰＥＮＡＮＡDI7kWHXzRk
} else if (word.charAt(0) < word.charAt(1)) {212Please respect copyright.ＰＥＮＡＮＡy3RFBX1Wju
String reversedWord = "" + word.charAt(1) + word.charAt(0);212Please respect copyright.ＰＥＮＡＮＡWp0r71GTxv
if (count.containsKey(reversedWord)) {212Please respect copyright.ＰＥＮＡＮＡYMIPmyKa6D
answer += 2 * Math.min(countOfTheWord, count.get(reversedWord));212Please respect copyright.ＰＥＮＡＮＡB4jCitDaU3
}212Please respect copyright.ＰＥＮＡＮＡxu3Usil1Sw
}212Please respect copyright.ＰＥＮＡＮＡh4i9arvyOu
}212Please respect copyright.ＰＥＮＡＮＡGO6kVxtiBQ
if (central) {212Please respect copyright.ＰＥＮＡＮＡWoBsihYsI0
answer++;212Please respect copyright.ＰＥＮＡＮＡ9wPWSrKGo8
}212Please respect copyright.ＰＥＮＡＮＡUttH63TGCq
return 2 * answer;212Please respect copyright.ＰＥＮＡＮＡo7r6YiNP1R
}212Please respect copyright.ＰＥＮＡＮＡ5Oqb12TLqj
}
2: A Two-Dimensional Array Approach
class Solution {212Please respect copyright.ＰＥＮＡＮＡ6sfmt2YGRK
public int longestPalindrome(String[] words) {212Please respect copyright.ＰＥＮＡＮＡVEIlngQt4h
final int alphabetSize = 26;212Please respect copyright.ＰＥＮＡＮＡC7ROHRCvdx
int[][] count = new int[alphabetSize][alphabetSize];212Please respect copyright.ＰＥＮＡＮＡjMX4PlNRBe
// Count the number of occurrences of each word using a two-dimensional array. 212Please respect copyright.ＰＥＮＡＮＡz1cbtJduHY
for (String word : words) {212Please respect copyright.ＰＥＮＡＮＡ72nRYdgSSv
count[word.charAt(0) - 'a'][word.charAt(1) - 'a']++;212Please respect copyright.ＰＥＮＡＮＡYWQnx1BvIp
}212Please respect copyright.ＰＥＮＡＮＡlBnM37N37y
// The answer will denote the number of words in the final string and the boolean variable central will denote whether we have a central word212Please respect copyright.ＰＥＮＡＮＡ1XNbEZHd6C
int answer = 0;212Please respect copyright.ＰＥＮＡＮＡw9N735tLG0
boolean central = false;212Please respect copyright.ＰＥＮＡＮＡvThj9cxkkk
for (int i = 0; i < alphabetSize; i++) {212Please respect copyright.ＰＥＮＡＮＡF9fTpkEajA
if (count[i][i] % 2 == 0) {212Please respect copyright.ＰＥＮＡＮＡBWdYfptpNP
answer += count[i][i];212Please respect copyright.ＰＥＮＡＮＡIpcjpGwSXx
} else {212Please respect copyright.ＰＥＮＡＮＡSJHqWMwwU8
answer += count[i][i] - 1;212Please respect copyright.ＰＥＮＡＮＡu7Mb1T96Pg
central = true;212Please respect copyright.ＰＥＮＡＮＡBfrWcHMykC
}212Please respect copyright.ＰＥＮＡＮＡ0no5dibrBe
for (int j = i + 1; j < alphabetSize; j++) {212Please respect copyright.ＰＥＮＡＮＡP6dYqZijMh
answer += 2 * Math.min(count[i][j], count[j][i]);212Please respect copyright.ＰＥＮＡＮＡB10khUc3P0
}212Please respect copyright.ＰＥＮＡＮＡdZRG0wsjBz
}212Please respect copyright.ＰＥＮＡＮＡWGmPi7jXor
if (central) {212Please respect copyright.ＰＥＮＡＮＡ586YXNp3qt
answer++;212Please respect copyright.ＰＥＮＡＮＡlpKbFvVwhA
}212Please respect copyright.ＰＥＮＡＮＡxUo2QEXDDD
return 2 * answer;212Please respect copyright.ＰＥＮＡＮＡrWK0xZ2ei5
}212Please respect copyright.ＰＥＮＡＮＡ7CT8GEf0ZT
}
212Please respect copyright.ＰＥＮＡＮＡwzU0DUWP6X
