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 {259Please respect copyright.ＰＥＮＡＮＡ3Lgwx2lEjC
public int longestPalindrome(String[] words) {259Please respect copyright.ＰＥＮＡＮＡi2dR2q9bT4
HashMap<String, Integer> count = new HashMap<String, Integer>();259Please respect copyright.ＰＥＮＡＮＡsLPCPJvi3h
// Count the number of occurrences of each word using a hashmap259Please respect copyright.ＰＥＮＡＮＡwgxwg0Mdkv
for (String word : words) {259Please respect copyright.ＰＥＮＡＮＡOpArCZ2CY4
Integer countOfTheWord = count.get(word);259Please respect copyright.ＰＥＮＡＮＡYQoACuRBk2
if (countOfTheWord == null) {259Please respect copyright.ＰＥＮＡＮＡppUyFObDD2
count.put(word, 1);259Please respect copyright.ＰＥＮＡＮＡRFbZlfHbdy
} else {259Please respect copyright.ＰＥＮＡＮＡAZjFjUemDu
count.put(word, countOfTheWord + 1);259Please respect copyright.ＰＥＮＡＮＡWFVv7hW37r
}259Please respect copyright.ＰＥＮＡＮＡ9IsvpBHiUb
}259Please respect copyright.ＰＥＮＡＮＡuAhpKEf2JE
// 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 word259Please respect copyright.ＰＥＮＡＮＡj2v0xFm5fZ
int answer = 0;259Please respect copyright.ＰＥＮＡＮＡBu7taNqJXr
boolean central = false;259Please respect copyright.ＰＥＮＡＮＡU8EA5L3TqE
for (Map.Entry<String, Integer> entry : count.entrySet()) {259Please respect copyright.ＰＥＮＡＮＡWqLIQ6J7QH
String word = entry.getKey();259Please respect copyright.ＰＥＮＡＮＡgMsbc6aW6c
int countOfTheWord = entry.getValue();259Please respect copyright.ＰＥＮＡＮＡTvxtteuEDy
// if the word is a palindrome259Please respect copyright.ＰＥＮＡＮＡhZ4O9Z59f2
if (word.charAt(0) == word.charAt(1)) {259Please respect copyright.ＰＥＮＡＮＡbtKp2tk2tV
if (countOfTheWord % 2 == 0) {259Please respect copyright.ＰＥＮＡＮＡx5VdTWE1DY
answer += countOfTheWord;259Please respect copyright.ＰＥＮＡＮＡ9JGmF1ZjkF
} else {259Please respect copyright.ＰＥＮＡＮＡENx0nku2G7
answer += countOfTheWord - 1;259Please respect copyright.ＰＥＮＡＮＡg0hvRPJurJ
central = true;259Please respect copyright.ＰＥＮＡＮＡBmgCkm12rG
}259Please respect copyright.ＰＥＮＡＮＡiCWBWfFYUL
// consider a pair of non-palindrome words such that one is the reverse of another259Please respect copyright.ＰＥＮＡＮＡq4soyckB4g
} else if (word.charAt(0) < word.charAt(1)) {259Please respect copyright.ＰＥＮＡＮＡM939QjD1lb
String reversedWord = "" + word.charAt(1) + word.charAt(0);259Please respect copyright.ＰＥＮＡＮＡxv0EsgHCUI
if (count.containsKey(reversedWord)) {259Please respect copyright.ＰＥＮＡＮＡjyiGfWMCst
answer += 2 * Math.min(countOfTheWord, count.get(reversedWord));259Please respect copyright.ＰＥＮＡＮＡduWFOS7dE1
}259Please respect copyright.ＰＥＮＡＮＡKhtUyQZ9x0
}259Please respect copyright.ＰＥＮＡＮＡdbhJlFDN40
}259Please respect copyright.ＰＥＮＡＮＡPurPylGi1i
if (central) {259Please respect copyright.ＰＥＮＡＮＡvh49ANMj9G
answer++;259Please respect copyright.ＰＥＮＡＮＡmXyctLRjQq
}259Please respect copyright.ＰＥＮＡＮＡDZImslKoby
return 2 * answer;259Please respect copyright.ＰＥＮＡＮＡgTrx7pIoxQ
}259Please respect copyright.ＰＥＮＡＮＡ1aUjpgM0pa
}
2: A Two-Dimensional Array Approach
class Solution {259Please respect copyright.ＰＥＮＡＮＡwzIRH5nwNg
public int longestPalindrome(String[] words) {259Please respect copyright.ＰＥＮＡＮＡBdqaZwJbjF
final int alphabetSize = 26;259Please respect copyright.ＰＥＮＡＮＡifI1EU7LbY
int[][] count = new int[alphabetSize][alphabetSize];259Please respect copyright.ＰＥＮＡＮＡ8yxCOK5bWo
// Count the number of occurrences of each word using a two-dimensional array. 259Please respect copyright.ＰＥＮＡＮＡxu45yyYQwr
for (String word : words) {259Please respect copyright.ＰＥＮＡＮＡEVePA984eb
count[word.charAt(0) - 'a'][word.charAt(1) - 'a']++;259Please respect copyright.ＰＥＮＡＮＡC7Ty3HA2GL
}259Please respect copyright.ＰＥＮＡＮＡ6teZeKzh6n
// The answer will denote the number of words in the final string and the boolean variable central will denote whether we have a central word259Please respect copyright.ＰＥＮＡＮＡ8TSxpu0Y9Y
int answer = 0;259Please respect copyright.ＰＥＮＡＮＡkmQKkDMypW
boolean central = false;259Please respect copyright.ＰＥＮＡＮＡViO6WLGOVm
for (int i = 0; i < alphabetSize; i++) {259Please respect copyright.ＰＥＮＡＮＡvxmvOlEBOV
if (count[i][i] % 2 == 0) {259Please respect copyright.ＰＥＮＡＮＡpH263SPGtf
answer += count[i][i];259Please respect copyright.ＰＥＮＡＮＡs7a4lvizp2
} else {259Please respect copyright.ＰＥＮＡＮＡoUPM7D090I
answer += count[i][i] - 1;259Please respect copyright.ＰＥＮＡＮＡeDhsVe2WCQ
central = true;259Please respect copyright.ＰＥＮＡＮＡbvkYKUUBSi
}259Please respect copyright.ＰＥＮＡＮＡcVT3iZ2L0K
for (int j = i + 1; j < alphabetSize; j++) {259Please respect copyright.ＰＥＮＡＮＡrdy7eGRlld
answer += 2 * Math.min(count[i][j], count[j][i]);259Please respect copyright.ＰＥＮＡＮＡTNlJOmR0Q0
}259Please respect copyright.ＰＥＮＡＮＡAOqPCMEQ6P
}259Please respect copyright.ＰＥＮＡＮＡVBC5t8VgIb
if (central) {259Please respect copyright.ＰＥＮＡＮＡc045mIzfuj
answer++;259Please respect copyright.ＰＥＮＡＮＡppLQniogUs
}259Please respect copyright.ＰＥＮＡＮＡz7Ju84eCcr
return 2 * answer;259Please respect copyright.ＰＥＮＡＮＡDOkNWV9NO3
}259Please respect copyright.ＰＥＮＡＮＡbk1jzz5oBG
}
259Please respect copyright.ＰＥＮＡＮＡvUBTZ5OLT0
