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 {144Please respect copyright.ＰＥＮＡＮＡNt7Qe0rmup
public int longestPalindrome(String[] words) {144Please respect copyright.ＰＥＮＡＮＡAaHGwxljiY
HashMap<String, Integer> count = new HashMap<String, Integer>();144Please respect copyright.ＰＥＮＡＮＡyEkLSOvE2Q
// Count the number of occurrences of each word using a hashmap144Please respect copyright.ＰＥＮＡＮＡEcmNdNlcUM
for (String word : words) {144Please respect copyright.ＰＥＮＡＮＡSSB0V6OxAF
Integer countOfTheWord = count.get(word);144Please respect copyright.ＰＥＮＡＮＡbSBPb8ZYjB
if (countOfTheWord == null) {144Please respect copyright.ＰＥＮＡＮＡtcNcfBnB12
count.put(word, 1);144Please respect copyright.ＰＥＮＡＮＡf5jMIUdGee
} else {144Please respect copyright.ＰＥＮＡＮＡZbV8MmYy8y
count.put(word, countOfTheWord + 1);144Please respect copyright.ＰＥＮＡＮＡOUiyuTBqo4
}144Please respect copyright.ＰＥＮＡＮＡXmyLlY0qrq
}144Please respect copyright.ＰＥＮＡＮＡCFsZYDOnHn
// 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 word144Please respect copyright.ＰＥＮＡＮＡ7kk3Hqw3YZ
int answer = 0;144Please respect copyright.ＰＥＮＡＮＡvuBEKfq3Gj
boolean central = false;144Please respect copyright.ＰＥＮＡＮＡ2FU2sA4ldw
for (Map.Entry<String, Integer> entry : count.entrySet()) {144Please respect copyright.ＰＥＮＡＮＡIvhSzIjXqu
String word = entry.getKey();144Please respect copyright.ＰＥＮＡＮＡs7oHT9CrZY
int countOfTheWord = entry.getValue();144Please respect copyright.ＰＥＮＡＮＡriScl5jRgx
// if the word is a palindrome144Please respect copyright.ＰＥＮＡＮＡiVu4IcZ8WN
if (word.charAt(0) == word.charAt(1)) {144Please respect copyright.ＰＥＮＡＮＡl7AK0gmQSC
if (countOfTheWord % 2 == 0) {144Please respect copyright.ＰＥＮＡＮＡ6BNkAh2p9I
answer += countOfTheWord;144Please respect copyright.ＰＥＮＡＮＡnkC3ZEU2QS
} else {144Please respect copyright.ＰＥＮＡＮＡqHUbbuIo9X
answer += countOfTheWord - 1;144Please respect copyright.ＰＥＮＡＮＡb803X2ySEK
central = true;144Please respect copyright.ＰＥＮＡＮＡjWlFGaOirF
}144Please respect copyright.ＰＥＮＡＮＡBJJKMzPz2f
// consider a pair of non-palindrome words such that one is the reverse of another144Please respect copyright.ＰＥＮＡＮＡMB6iB1fzfF
} else if (word.charAt(0) < word.charAt(1)) {144Please respect copyright.ＰＥＮＡＮＡfMvdrxZ2up
String reversedWord = "" + word.charAt(1) + word.charAt(0);144Please respect copyright.ＰＥＮＡＮＡdquPnM8ZpQ
if (count.containsKey(reversedWord)) {144Please respect copyright.ＰＥＮＡＮＡrlGvXh8dnG
answer += 2 * Math.min(countOfTheWord, count.get(reversedWord));144Please respect copyright.ＰＥＮＡＮＡ5O6ixBjjuW
}144Please respect copyright.ＰＥＮＡＮＡU7eRFjQJzS
}144Please respect copyright.ＰＥＮＡＮＡtUU4hWSxuh
}144Please respect copyright.ＰＥＮＡＮＡ12ghlTtnUr
if (central) {144Please respect copyright.ＰＥＮＡＮＡqbogn9GCim
answer++;144Please respect copyright.ＰＥＮＡＮＡywEwOFoUDL
}144Please respect copyright.ＰＥＮＡＮＡh1xphLNxGU
return 2 * answer;144Please respect copyright.ＰＥＮＡＮＡWpQrNH6FjC
}144Please respect copyright.ＰＥＮＡＮＡTNQMF4y4xU
}
2: A Two-Dimensional Array Approach
class Solution {144Please respect copyright.ＰＥＮＡＮＡJAI0easb0s
public int longestPalindrome(String[] words) {144Please respect copyright.ＰＥＮＡＮＡ0Z9kuiS8EI
final int alphabetSize = 26;144Please respect copyright.ＰＥＮＡＮＡF1bAjgFMcG
int[][] count = new int[alphabetSize][alphabetSize];144Please respect copyright.ＰＥＮＡＮＡ0NONwk9vEp
// Count the number of occurrences of each word using a two-dimensional array. 144Please respect copyright.ＰＥＮＡＮＡzc7b9P3B1e
for (String word : words) {144Please respect copyright.ＰＥＮＡＮＡw33B9hAwJT
count[word.charAt(0) - 'a'][word.charAt(1) - 'a']++;144Please respect copyright.ＰＥＮＡＮＡwXDJxPkHwA
}144Please respect copyright.ＰＥＮＡＮＡljY72jyZFk
// The answer will denote the number of words in the final string and the boolean variable central will denote whether we have a central word144Please respect copyright.ＰＥＮＡＮＡZ3sZgqP5fp
int answer = 0;144Please respect copyright.ＰＥＮＡＮＡGEFogsFcPQ
boolean central = false;144Please respect copyright.ＰＥＮＡＮＡMMcYppifck
for (int i = 0; i < alphabetSize; i++) {144Please respect copyright.ＰＥＮＡＮＡIEz8v6PbNT
if (count[i][i] % 2 == 0) {144Please respect copyright.ＰＥＮＡＮＡfWULR9GQ0b
answer += count[i][i];144Please respect copyright.ＰＥＮＡＮＡNmOx0UMIHl
} else {144Please respect copyright.ＰＥＮＡＮＡcATcaBXaZB
answer += count[i][i] - 1;144Please respect copyright.ＰＥＮＡＮＡJQIifJyY6t
central = true;144Please respect copyright.ＰＥＮＡＮＡnkugoJs0jn
}144Please respect copyright.ＰＥＮＡＮＡJwuGvJMhdc
for (int j = i + 1; j < alphabetSize; j++) {144Please respect copyright.ＰＥＮＡＮＡbpQBt7svNe
answer += 2 * Math.min(count[i][j], count[j][i]);144Please respect copyright.ＰＥＮＡＮＡ3yWQU1tqrQ
}144Please respect copyright.ＰＥＮＡＮＡbdlmRNikte
}144Please respect copyright.ＰＥＮＡＮＡ3fT8qRq83q
if (central) {144Please respect copyright.ＰＥＮＡＮＡ357w5Vxjo4
answer++;144Please respect copyright.ＰＥＮＡＮＡcJgWPtrWIt
}144Please respect copyright.ＰＥＮＡＮＡu6hzcs0EpN
return 2 * answer;144Please respect copyright.ＰＥＮＡＮＡrnQgydtP2P
}144Please respect copyright.ＰＥＮＡＮＡ0zdD2R79Fj
}
144Please respect copyright.ＰＥＮＡＮＡLO4N73e0iC
