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 {160Please respect copyright.ＰＥＮＡＮＡYXhO52fmw1
public int longestPalindrome(String[] words) {160Please respect copyright.ＰＥＮＡＮＡRiv9sDj2PP
HashMap<String, Integer> count = new HashMap<String, Integer>();160Please respect copyright.ＰＥＮＡＮＡtjghPcNtOL
// Count the number of occurrences of each word using a hashmap160Please respect copyright.ＰＥＮＡＮＡWEtEnWZftl
for (String word : words) {160Please respect copyright.ＰＥＮＡＮＡvN1TKg6gkN
Integer countOfTheWord = count.get(word);160Please respect copyright.ＰＥＮＡＮＡF98pfLalIq
if (countOfTheWord == null) {160Please respect copyright.ＰＥＮＡＮＡ3mklskvwgE
count.put(word, 1);160Please respect copyright.ＰＥＮＡＮＡxkpu8IOEoZ
} else {160Please respect copyright.ＰＥＮＡＮＡRkwboxHE4Y
count.put(word, countOfTheWord + 1);160Please respect copyright.ＰＥＮＡＮＡNF1qmLmeMs
}160Please respect copyright.ＰＥＮＡＮＡoQx4l1osKz
}160Please respect copyright.ＰＥＮＡＮＡFZ4tpLGnRq
// 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 word160Please respect copyright.ＰＥＮＡＮＡCQtbLUSK7w
int answer = 0;160Please respect copyright.ＰＥＮＡＮＡ31433a5ZS5
boolean central = false;160Please respect copyright.ＰＥＮＡＮＡEiDCQbGwCb
for (Map.Entry<String, Integer> entry : count.entrySet()) {160Please respect copyright.ＰＥＮＡＮＡGjZb0J4gy2
String word = entry.getKey();160Please respect copyright.ＰＥＮＡＮＡfOh9s8akXC
int countOfTheWord = entry.getValue();160Please respect copyright.ＰＥＮＡＮＡ5mJT4zCze0
// if the word is a palindrome160Please respect copyright.ＰＥＮＡＮＡGxu6OyWoJu
if (word.charAt(0) == word.charAt(1)) {160Please respect copyright.ＰＥＮＡＮＡt3Zfb4BpIW
if (countOfTheWord % 2 == 0) {160Please respect copyright.ＰＥＮＡＮＡXKiUVstGbR
answer += countOfTheWord;160Please respect copyright.ＰＥＮＡＮＡ8wgPMER90V
} else {160Please respect copyright.ＰＥＮＡＮＡ0xxKrxLnS6
answer += countOfTheWord - 1;160Please respect copyright.ＰＥＮＡＮＡcGMZGJJk8C
central = true;160Please respect copyright.ＰＥＮＡＮＡKZvSF8Drnv
}160Please respect copyright.ＰＥＮＡＮＡSXPEgV1oLa
// consider a pair of non-palindrome words such that one is the reverse of another160Please respect copyright.ＰＥＮＡＮＡAiVI540sBg
} else if (word.charAt(0) < word.charAt(1)) {160Please respect copyright.ＰＥＮＡＮＡ1ibmUtxXKY
String reversedWord = "" + word.charAt(1) + word.charAt(0);160Please respect copyright.ＰＥＮＡＮＡBKdgQdyYuk
if (count.containsKey(reversedWord)) {160Please respect copyright.ＰＥＮＡＮＡrtEZknVUaz
answer += 2 * Math.min(countOfTheWord, count.get(reversedWord));160Please respect copyright.ＰＥＮＡＮＡmp3Oq6BDad
}160Please respect copyright.ＰＥＮＡＮＡHIEfeQ57du
}160Please respect copyright.ＰＥＮＡＮＡBZWuDj3XyR
}160Please respect copyright.ＰＥＮＡＮＡjnGMgUd5kb
if (central) {160Please respect copyright.ＰＥＮＡＮＡBvu1vQYcxN
answer++;160Please respect copyright.ＰＥＮＡＮＡ8eGumNvuV1
}160Please respect copyright.ＰＥＮＡＮＡTJvQwev0Hx
return 2 * answer;160Please respect copyright.ＰＥＮＡＮＡgma5wiz9mw
}160Please respect copyright.ＰＥＮＡＮＡQWOpQuiylG
}
2: A Two-Dimensional Array Approach
class Solution {160Please respect copyright.ＰＥＮＡＮＡgrLNWx3f5V
public int longestPalindrome(String[] words) {160Please respect copyright.ＰＥＮＡＮＡB8agKdGXru
final int alphabetSize = 26;160Please respect copyright.ＰＥＮＡＮＡOgLGYcKGZH
int[][] count = new int[alphabetSize][alphabetSize];160Please respect copyright.ＰＥＮＡＮＡO4lJGgZQkN
// Count the number of occurrences of each word using a two-dimensional array. 160Please respect copyright.ＰＥＮＡＮＡrJORk0TrA0
for (String word : words) {160Please respect copyright.ＰＥＮＡＮＡ8l2xeBtQwt
count[word.charAt(0) - 'a'][word.charAt(1) - 'a']++;160Please respect copyright.ＰＥＮＡＮＡ2WOMEUCzXU
}160Please respect copyright.ＰＥＮＡＮＡ3cMIYWo5k8
// The answer will denote the number of words in the final string and the boolean variable central will denote whether we have a central word160Please respect copyright.ＰＥＮＡＮＡWzAQCqpu62
int answer = 0;160Please respect copyright.ＰＥＮＡＮＡvVbdXDcdAX
boolean central = false;160Please respect copyright.ＰＥＮＡＮＡJcc8Pl1792
for (int i = 0; i < alphabetSize; i++) {160Please respect copyright.ＰＥＮＡＮＡxx0wZ1HyUv
if (count[i][i] % 2 == 0) {160Please respect copyright.ＰＥＮＡＮＡjdisVcbnMZ
answer += count[i][i];160Please respect copyright.ＰＥＮＡＮＡmagGxEdS5Y
} else {160Please respect copyright.ＰＥＮＡＮＡmGkU8vnRnF
answer += count[i][i] - 1;160Please respect copyright.ＰＥＮＡＮＡhP4dW8ciSy
central = true;160Please respect copyright.ＰＥＮＡＮＡVZ13pnOMxX
}160Please respect copyright.ＰＥＮＡＮＡak19litAeA
for (int j = i + 1; j < alphabetSize; j++) {160Please respect copyright.ＰＥＮＡＮＡcULOmhbsIT
answer += 2 * Math.min(count[i][j], count[j][i]);160Please respect copyright.ＰＥＮＡＮＡQrP4846OkS
}160Please respect copyright.ＰＥＮＡＮＡJnCKTPcY6S
}160Please respect copyright.ＰＥＮＡＮＡHFx0pKcFZi
if (central) {160Please respect copyright.ＰＥＮＡＮＡOmXHmdlBe0
answer++;160Please respect copyright.ＰＥＮＡＮＡf3NLmskx6Y
}160Please respect copyright.ＰＥＮＡＮＡ3tx5mTZ32j
return 2 * answer;160Please respect copyright.ＰＥＮＡＮＡ85fmADvsjo
}160Please respect copyright.ＰＥＮＡＮＡsIKHbF1rTG
}
160Please respect copyright.ＰＥＮＡＮＡhSAZy03Qkz
