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 {217Please respect copyright.ＰＥＮＡＮＡgxTV0b0M0k
public int longestPalindrome(String[] words) {217Please respect copyright.ＰＥＮＡＮＡrv8lXzLHmX
HashMap<String, Integer> count = new HashMap<String, Integer>();217Please respect copyright.ＰＥＮＡＮＡZpTqeESGsx
// Count the number of occurrences of each word using a hashmap217Please respect copyright.ＰＥＮＡＮＡ0Qh6f9OzAb
for (String word : words) {217Please respect copyright.ＰＥＮＡＮＡlhNhGQ5FSZ
Integer countOfTheWord = count.get(word);217Please respect copyright.ＰＥＮＡＮＡNLMGsHx8Of
if (countOfTheWord == null) {217Please respect copyright.ＰＥＮＡＮＡpeXlQBXGJ6
count.put(word, 1);217Please respect copyright.ＰＥＮＡＮＡO99ly0biYL
} else {217Please respect copyright.ＰＥＮＡＮＡIuiQV5zaaf
count.put(word, countOfTheWord + 1);217Please respect copyright.ＰＥＮＡＮＡJRC2kI1gFb
}217Please respect copyright.ＰＥＮＡＮＡLvnNUGZnht
}217Please respect copyright.ＰＥＮＡＮＡdNzjHvJhBT
// 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 word217Please respect copyright.ＰＥＮＡＮＡh47BbopQ7f
int answer = 0;217Please respect copyright.ＰＥＮＡＮＡY2YhmpT73z
boolean central = false;217Please respect copyright.ＰＥＮＡＮＡsqGSG9zSYi
for (Map.Entry<String, Integer> entry : count.entrySet()) {217Please respect copyright.ＰＥＮＡＮＡGdK3qFRYU4
String word = entry.getKey();217Please respect copyright.ＰＥＮＡＮＡ8WrEPE0xPL
int countOfTheWord = entry.getValue();217Please respect copyright.ＰＥＮＡＮＡwsBMpmDYWK
// if the word is a palindrome217Please respect copyright.ＰＥＮＡＮＡ7HPXyYHt35
if (word.charAt(0) == word.charAt(1)) {217Please respect copyright.ＰＥＮＡＮＡAVo3MXTyM8
if (countOfTheWord % 2 == 0) {217Please respect copyright.ＰＥＮＡＮＡgkuK5QWKrK
answer += countOfTheWord;217Please respect copyright.ＰＥＮＡＮＡFcD750odxZ
} else {217Please respect copyright.ＰＥＮＡＮＡNbzmYjmZ3o
answer += countOfTheWord - 1;217Please respect copyright.ＰＥＮＡＮＡ96xmCCwJ3V
central = true;217Please respect copyright.ＰＥＮＡＮＡ8hY9oUEcta
}217Please respect copyright.ＰＥＮＡＮＡyjmnZsohYK
// consider a pair of non-palindrome words such that one is the reverse of another217Please respect copyright.ＰＥＮＡＮＡl4wQJTKeFD
} else if (word.charAt(0) < word.charAt(1)) {217Please respect copyright.ＰＥＮＡＮＡeE1Yxf6ZHa
String reversedWord = "" + word.charAt(1) + word.charAt(0);217Please respect copyright.ＰＥＮＡＮＡLrOmffjEbu
if (count.containsKey(reversedWord)) {217Please respect copyright.ＰＥＮＡＮＡjYj13ixj7g
answer += 2 * Math.min(countOfTheWord, count.get(reversedWord));217Please respect copyright.ＰＥＮＡＮＡvd1WICnRVw
}217Please respect copyright.ＰＥＮＡＮＡfoKZ1fC6Zi
}217Please respect copyright.ＰＥＮＡＮＡJhXET0uOhd
}217Please respect copyright.ＰＥＮＡＮＡLAuKLjtHki
if (central) {217Please respect copyright.ＰＥＮＡＮＡE2jDC5dajJ
answer++;217Please respect copyright.ＰＥＮＡＮＡ6mjtkrV0ll
}217Please respect copyright.ＰＥＮＡＮＡpmmOP8yOtf
return 2 * answer;217Please respect copyright.ＰＥＮＡＮＡxGPlRbJDMy
}217Please respect copyright.ＰＥＮＡＮＡxif2fdzuvi
}
2: A Two-Dimensional Array Approach
class Solution {217Please respect copyright.ＰＥＮＡＮＡPWH4uVaZOx
public int longestPalindrome(String[] words) {217Please respect copyright.ＰＥＮＡＮＡUro4DSje9F
final int alphabetSize = 26;217Please respect copyright.ＰＥＮＡＮＡRsuJDcrGBe
int[][] count = new int[alphabetSize][alphabetSize];217Please respect copyright.ＰＥＮＡＮＡ290g7exOeL
// Count the number of occurrences of each word using a two-dimensional array. 217Please respect copyright.ＰＥＮＡＮＡMpMSwZ4woX
for (String word : words) {217Please respect copyright.ＰＥＮＡＮＡ1cSadF7NsC
count[word.charAt(0) - 'a'][word.charAt(1) - 'a']++;217Please respect copyright.ＰＥＮＡＮＡgxggdmmxqz
}217Please respect copyright.ＰＥＮＡＮＡo4iq40b6yk
// The answer will denote the number of words in the final string and the boolean variable central will denote whether we have a central word217Please respect copyright.ＰＥＮＡＮＡvCTASOul9k
int answer = 0;217Please respect copyright.ＰＥＮＡＮＡngdWZtOXZV
boolean central = false;217Please respect copyright.ＰＥＮＡＮＡZlwFEJ4fEo
for (int i = 0; i < alphabetSize; i++) {217Please respect copyright.ＰＥＮＡＮＡnTXxDv5o47
if (count[i][i] % 2 == 0) {217Please respect copyright.ＰＥＮＡＮＡzqMJXiYMJA
answer += count[i][i];217Please respect copyright.ＰＥＮＡＮＡDmCCSF0pe3
} else {217Please respect copyright.ＰＥＮＡＮＡUHwbTe7Cxh
answer += count[i][i] - 1;217Please respect copyright.ＰＥＮＡＮＡ0DJmvXsvy3
central = true;217Please respect copyright.ＰＥＮＡＮＡ8TURBLaFm1
}217Please respect copyright.ＰＥＮＡＮＡ29PqUyQfUt
for (int j = i + 1; j < alphabetSize; j++) {217Please respect copyright.ＰＥＮＡＮＡLBaAuSOnE8
answer += 2 * Math.min(count[i][j], count[j][i]);217Please respect copyright.ＰＥＮＡＮＡNF8chY3cUJ
}217Please respect copyright.ＰＥＮＡＮＡFoJ1p33paP
}217Please respect copyright.ＰＥＮＡＮＡRSRoc41JKG
if (central) {217Please respect copyright.ＰＥＮＡＮＡIX3ouExMKV
answer++;217Please respect copyright.ＰＥＮＡＮＡIdPkTlogZT
}217Please respect copyright.ＰＥＮＡＮＡ0VJq8eq99F
return 2 * answer;217Please respect copyright.ＰＥＮＡＮＡg9ZcgFKgHp
}217Please respect copyright.ＰＥＮＡＮＡFto8iah5ky
}
217Please respect copyright.ＰＥＮＡＮＡCEr2o99LA0
