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 {189Please respect copyright.ＰＥＮＡＮＡetkSJK4E2D
public int longestPalindrome(String[] words) {189Please respect copyright.ＰＥＮＡＮＡSECj4XTWuS
HashMap<String, Integer> count = new HashMap<String, Integer>();189Please respect copyright.ＰＥＮＡＮＡLibnEjD9qQ
// Count the number of occurrences of each word using a hashmap189Please respect copyright.ＰＥＮＡＮＡBmq7GVcWHR
for (String word : words) {189Please respect copyright.ＰＥＮＡＮＡAiLhdrZivv
Integer countOfTheWord = count.get(word);189Please respect copyright.ＰＥＮＡＮＡnUq12rGxUt
if (countOfTheWord == null) {189Please respect copyright.ＰＥＮＡＮＡy2a0sq8wI8
count.put(word, 1);189Please respect copyright.ＰＥＮＡＮＡksgNbJiF9l
} else {189Please respect copyright.ＰＥＮＡＮＡJhyybFqVKc
count.put(word, countOfTheWord + 1);189Please respect copyright.ＰＥＮＡＮＡudbt1xgucs
}189Please respect copyright.ＰＥＮＡＮＡ41qCVWeUxX
}189Please respect copyright.ＰＥＮＡＮＡHZetJ1wo6o
// 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 word189Please respect copyright.ＰＥＮＡＮＡcU4dJoCi2J
int answer = 0;189Please respect copyright.ＰＥＮＡＮＡyQA19J8QQR
boolean central = false;189Please respect copyright.ＰＥＮＡＮＡctRGca34vB
for (Map.Entry<String, Integer> entry : count.entrySet()) {189Please respect copyright.ＰＥＮＡＮＡV40rKKdfQ7
String word = entry.getKey();189Please respect copyright.ＰＥＮＡＮＡ9d9OO7gNeq
int countOfTheWord = entry.getValue();189Please respect copyright.ＰＥＮＡＮＡWbPTkV8V6e
// if the word is a palindrome189Please respect copyright.ＰＥＮＡＮＡwLmE83JLLA
if (word.charAt(0) == word.charAt(1)) {189Please respect copyright.ＰＥＮＡＮＡoRODWHubOJ
if (countOfTheWord % 2 == 0) {189Please respect copyright.ＰＥＮＡＮＡk6uz0B7DIP
answer += countOfTheWord;189Please respect copyright.ＰＥＮＡＮＡQ4cZBw9ycw
} else {189Please respect copyright.ＰＥＮＡＮＡZgFGygCTq8
answer += countOfTheWord - 1;189Please respect copyright.ＰＥＮＡＮＡDxbJeZlfCj
central = true;189Please respect copyright.ＰＥＮＡＮＡkwzbinWByW
}189Please respect copyright.ＰＥＮＡＮＡLDnBRcrHQo
// consider a pair of non-palindrome words such that one is the reverse of another189Please respect copyright.ＰＥＮＡＮＡ2L8j5y0KFm
} else if (word.charAt(0) < word.charAt(1)) {189Please respect copyright.ＰＥＮＡＮＡwczl1kFz3i
String reversedWord = "" + word.charAt(1) + word.charAt(0);189Please respect copyright.ＰＥＮＡＮＡpvQlqH9tNU
if (count.containsKey(reversedWord)) {189Please respect copyright.ＰＥＮＡＮＡFZPc6pH5ao
answer += 2 * Math.min(countOfTheWord, count.get(reversedWord));189Please respect copyright.ＰＥＮＡＮＡE3X4ow2Own
}189Please respect copyright.ＰＥＮＡＮＡKBVNMS3udm
}189Please respect copyright.ＰＥＮＡＮＡXlnmTLgoXv
}189Please respect copyright.ＰＥＮＡＮＡBa7eP5Accz
if (central) {189Please respect copyright.ＰＥＮＡＮＡ9FJ1ZZQlPA
answer++;189Please respect copyright.ＰＥＮＡＮＡv5sXRWZN2D
}189Please respect copyright.ＰＥＮＡＮＡMsxaMGXdZg
return 2 * answer;189Please respect copyright.ＰＥＮＡＮＡTsvC3whxJN
}189Please respect copyright.ＰＥＮＡＮＡGI9S4BZJSh
}
2: A Two-Dimensional Array Approach
class Solution {189Please respect copyright.ＰＥＮＡＮＡJha1ApB4vu
public int longestPalindrome(String[] words) {189Please respect copyright.ＰＥＮＡＮＡdA7q5MmG5S
final int alphabetSize = 26;189Please respect copyright.ＰＥＮＡＮＡOXfLy4xU1M
int[][] count = new int[alphabetSize][alphabetSize];189Please respect copyright.ＰＥＮＡＮＡ5Ic2zfFAib
// Count the number of occurrences of each word using a two-dimensional array. 189Please respect copyright.ＰＥＮＡＮＡgjR33YmdZU
for (String word : words) {189Please respect copyright.ＰＥＮＡＮＡ3jSa48xRBy
count[word.charAt(0) - 'a'][word.charAt(1) - 'a']++;189Please respect copyright.ＰＥＮＡＮＡsBmQSRqQNz
}189Please respect copyright.ＰＥＮＡＮＡNQjj0gteAr
// The answer will denote the number of words in the final string and the boolean variable central will denote whether we have a central word189Please respect copyright.ＰＥＮＡＮＡI4TJHwru7I
int answer = 0;189Please respect copyright.ＰＥＮＡＮＡiRT4wJAhOh
boolean central = false;189Please respect copyright.ＰＥＮＡＮＡ41Hq6GVSFF
for (int i = 0; i < alphabetSize; i++) {189Please respect copyright.ＰＥＮＡＮＡwwV6nV5k3d
if (count[i][i] % 2 == 0) {189Please respect copyright.ＰＥＮＡＮＡJmpX4QI6XV
answer += count[i][i];189Please respect copyright.ＰＥＮＡＮＡnit1NhUpp0
} else {189Please respect copyright.ＰＥＮＡＮＡZZZbCA59A6
answer += count[i][i] - 1;189Please respect copyright.ＰＥＮＡＮＡkO60mCYf2E
central = true;189Please respect copyright.ＰＥＮＡＮＡOfF0xBASI3
}189Please respect copyright.ＰＥＮＡＮＡEtDCkkaiVu
for (int j = i + 1; j < alphabetSize; j++) {189Please respect copyright.ＰＥＮＡＮＡ9FHemmPfWn
answer += 2 * Math.min(count[i][j], count[j][i]);189Please respect copyright.ＰＥＮＡＮＡ6lyrHn9ZDX
}189Please respect copyright.ＰＥＮＡＮＡITY6nsNjkT
}189Please respect copyright.ＰＥＮＡＮＡdhdD3BuTi4
if (central) {189Please respect copyright.ＰＥＮＡＮＡQbJizn6SO5
answer++;189Please respect copyright.ＰＥＮＡＮＡYBF6znDZjF
}189Please respect copyright.ＰＥＮＡＮＡVkY8cKX3tA
return 2 * answer;189Please respect copyright.ＰＥＮＡＮＡsiACq6pkvi
}189Please respect copyright.ＰＥＮＡＮＡ1O7QjLQXCd
}
189Please respect copyright.ＰＥＮＡＮＡAWdtguJOb7
