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 {194Please respect copyright.ＰＥＮＡＮＡFpZBxyHB4H
public int longestPalindrome(String[] words) {194Please respect copyright.ＰＥＮＡＮＡnLrte1jZAt
HashMap<String, Integer> count = new HashMap<String, Integer>();194Please respect copyright.ＰＥＮＡＮＡXJQal559pP
// Count the number of occurrences of each word using a hashmap194Please respect copyright.ＰＥＮＡＮＡj2jx7PTEk4
for (String word : words) {194Please respect copyright.ＰＥＮＡＮＡS4ucrKzQLi
Integer countOfTheWord = count.get(word);194Please respect copyright.ＰＥＮＡＮＡsEpd8frZ2v
if (countOfTheWord == null) {194Please respect copyright.ＰＥＮＡＮＡUoxjE60lCB
count.put(word, 1);194Please respect copyright.ＰＥＮＡＮＡk76Ll68DwR
} else {194Please respect copyright.ＰＥＮＡＮＡMIhWsrkQem
count.put(word, countOfTheWord + 1);194Please respect copyright.ＰＥＮＡＮＡ4FcUvGChEA
}194Please respect copyright.ＰＥＮＡＮＡ310AQ0DE8a
}194Please respect copyright.ＰＥＮＡＮＡconzEBc7V3
// 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 word194Please respect copyright.ＰＥＮＡＮＡsCtRjWzE4Q
int answer = 0;194Please respect copyright.ＰＥＮＡＮＡtNhin1aQSp
boolean central = false;194Please respect copyright.ＰＥＮＡＮＡi3ULrvZQV5
for (Map.Entry<String, Integer> entry : count.entrySet()) {194Please respect copyright.ＰＥＮＡＮＡRMBli57mQ1
String word = entry.getKey();194Please respect copyright.ＰＥＮＡＮＡER1giB6vID
int countOfTheWord = entry.getValue();194Please respect copyright.ＰＥＮＡＮＡnBvcqxy4E4
// if the word is a palindrome194Please respect copyright.ＰＥＮＡＮＡdfHjp1xbJt
if (word.charAt(0) == word.charAt(1)) {194Please respect copyright.ＰＥＮＡＮＡOTepwW2M9W
if (countOfTheWord % 2 == 0) {194Please respect copyright.ＰＥＮＡＮＡV8H23HNo4M
answer += countOfTheWord;194Please respect copyright.ＰＥＮＡＮＡTTUZWFNgQt
} else {194Please respect copyright.ＰＥＮＡＮＡ6iy5qLUN5z
answer += countOfTheWord - 1;194Please respect copyright.ＰＥＮＡＮＡfSo4vMhNm9
central = true;194Please respect copyright.ＰＥＮＡＮＡPOUFgEiwFe
}194Please respect copyright.ＰＥＮＡＮＡyfpeiWWxnQ
// consider a pair of non-palindrome words such that one is the reverse of another194Please respect copyright.ＰＥＮＡＮＡGWxl8TGK19
} else if (word.charAt(0) < word.charAt(1)) {194Please respect copyright.ＰＥＮＡＮＡa29MqM32Xq
String reversedWord = "" + word.charAt(1) + word.charAt(0);194Please respect copyright.ＰＥＮＡＮＡ5LH0uGjvB2
if (count.containsKey(reversedWord)) {194Please respect copyright.ＰＥＮＡＮＡROS2lxxKUB
answer += 2 * Math.min(countOfTheWord, count.get(reversedWord));194Please respect copyright.ＰＥＮＡＮＡlw39t9OuRH
}194Please respect copyright.ＰＥＮＡＮＡbZL9zahLg6
}194Please respect copyright.ＰＥＮＡＮＡIQMsohiRBx
}194Please respect copyright.ＰＥＮＡＮＡKQ9CSbqkSR
if (central) {194Please respect copyright.ＰＥＮＡＮＡyh25c15U9d
answer++;194Please respect copyright.ＰＥＮＡＮＡTjV8jEsrd4
}194Please respect copyright.ＰＥＮＡＮＡmpFbunP9Sw
return 2 * answer;194Please respect copyright.ＰＥＮＡＮＡWiR8xHTyFk
}194Please respect copyright.ＰＥＮＡＮＡUI1asTagfP
}
2: A Two-Dimensional Array Approach
class Solution {194Please respect copyright.ＰＥＮＡＮＡ1e6j0jEgxF
public int longestPalindrome(String[] words) {194Please respect copyright.ＰＥＮＡＮＡCq15cbNFdc
final int alphabetSize = 26;194Please respect copyright.ＰＥＮＡＮＡpUHf4jmEdJ
int[][] count = new int[alphabetSize][alphabetSize];194Please respect copyright.ＰＥＮＡＮＡfspSjuZcJy
// Count the number of occurrences of each word using a two-dimensional array. 194Please respect copyright.ＰＥＮＡＮＡ37JEI5tDY0
for (String word : words) {194Please respect copyright.ＰＥＮＡＮＡe0aL3QJPH4
count[word.charAt(0) - 'a'][word.charAt(1) - 'a']++;194Please respect copyright.ＰＥＮＡＮＡc1dUSnP6GR
}194Please respect copyright.ＰＥＮＡＮＡblG076BXDH
// The answer will denote the number of words in the final string and the boolean variable central will denote whether we have a central word194Please respect copyright.ＰＥＮＡＮＡMczzip7rGX
int answer = 0;194Please respect copyright.ＰＥＮＡＮＡ3FpeloGmkI
boolean central = false;194Please respect copyright.ＰＥＮＡＮＡRj5iLnvJXW
for (int i = 0; i < alphabetSize; i++) {194Please respect copyright.ＰＥＮＡＮＡX1h9k9kLaH
if (count[i][i] % 2 == 0) {194Please respect copyright.ＰＥＮＡＮＡVMc2qlydTF
answer += count[i][i];194Please respect copyright.ＰＥＮＡＮＡgJETeWXb7H
} else {194Please respect copyright.ＰＥＮＡＮＡmUuMG0XsnU
answer += count[i][i] - 1;194Please respect copyright.ＰＥＮＡＮＡ9S4a2hlFwj
central = true;194Please respect copyright.ＰＥＮＡＮＡ9hCUS2LZhI
}194Please respect copyright.ＰＥＮＡＮＡyuKVsgS26t
for (int j = i + 1; j < alphabetSize; j++) {194Please respect copyright.ＰＥＮＡＮＡyA2KXXCgeJ
answer += 2 * Math.min(count[i][j], count[j][i]);194Please respect copyright.ＰＥＮＡＮＡ37uZaUkBVG
}194Please respect copyright.ＰＥＮＡＮＡJnZtfMA6MC
}194Please respect copyright.ＰＥＮＡＮＡ9EXBCgrKGs
if (central) {194Please respect copyright.ＰＥＮＡＮＡ2Oags2CvRb
answer++;194Please respect copyright.ＰＥＮＡＮＡnmXiYOHAXm
}194Please respect copyright.ＰＥＮＡＮＡWHy6ObYofH
return 2 * answer;194Please respect copyright.ＰＥＮＡＮＡSSpY1fqEYZ
}194Please respect copyright.ＰＥＮＡＮＡpC6gYvdzca
}
194Please respect copyright.ＰＥＮＡＮＡ431jS4tt1w
