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 {253Please respect copyright.ＰＥＮＡＮＡJ8DzClM80g
public int longestPalindrome(String[] words) {253Please respect copyright.ＰＥＮＡＮＡIaVbKIPIGe
HashMap<String, Integer> count = new HashMap<String, Integer>();253Please respect copyright.ＰＥＮＡＮＡQU6zj5vWI8
// Count the number of occurrences of each word using a hashmap253Please respect copyright.ＰＥＮＡＮＡlI3FpNoD95
for (String word : words) {253Please respect copyright.ＰＥＮＡＮＡMttElC5NEW
Integer countOfTheWord = count.get(word);253Please respect copyright.ＰＥＮＡＮＡ83lbU3n3cJ
if (countOfTheWord == null) {253Please respect copyright.ＰＥＮＡＮＡ03CvRGtMxH
count.put(word, 1);253Please respect copyright.ＰＥＮＡＮＡRwW2lKJA7e
} else {253Please respect copyright.ＰＥＮＡＮＡ2ivBEVjc3g
count.put(word, countOfTheWord + 1);253Please respect copyright.ＰＥＮＡＮＡTybzfQ946W
}253Please respect copyright.ＰＥＮＡＮＡsoJxZ78ziL
}253Please respect copyright.ＰＥＮＡＮＡYJMyOel0ca
// 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 word253Please respect copyright.ＰＥＮＡＮＡSnyPPLgDyd
int answer = 0;253Please respect copyright.ＰＥＮＡＮＡPUkGrFNEs5
boolean central = false;253Please respect copyright.ＰＥＮＡＮＡ747KGROd50
for (Map.Entry<String, Integer> entry : count.entrySet()) {253Please respect copyright.ＰＥＮＡＮＡ8COhE462aM
String word = entry.getKey();253Please respect copyright.ＰＥＮＡＮＡVpt66Z3RVi
int countOfTheWord = entry.getValue();253Please respect copyright.ＰＥＮＡＮＡlIpesiAymn
// if the word is a palindrome253Please respect copyright.ＰＥＮＡＮＡ6EZHOsZ1Fj
if (word.charAt(0) == word.charAt(1)) {253Please respect copyright.ＰＥＮＡＮＡiw4JpeP17h
if (countOfTheWord % 2 == 0) {253Please respect copyright.ＰＥＮＡＮＡchK6lwl8Q3
answer += countOfTheWord;253Please respect copyright.ＰＥＮＡＮＡfQiuWj8UCd
} else {253Please respect copyright.ＰＥＮＡＮＡh63TUho9Xu
answer += countOfTheWord - 1;253Please respect copyright.ＰＥＮＡＮＡ3l1HGAmMOP
central = true;253Please respect copyright.ＰＥＮＡＮＡEo0JIx4KzS
}253Please respect copyright.ＰＥＮＡＮＡKuXFVib6vC
// consider a pair of non-palindrome words such that one is the reverse of another253Please respect copyright.ＰＥＮＡＮＡOqHoVRsqE9
} else if (word.charAt(0) < word.charAt(1)) {253Please respect copyright.ＰＥＮＡＮＡg5kuA2fjZu
String reversedWord = "" + word.charAt(1) + word.charAt(0);253Please respect copyright.ＰＥＮＡＮＡDlgmWWLDTa
if (count.containsKey(reversedWord)) {253Please respect copyright.ＰＥＮＡＮＡ6G3hnUNU22
answer += 2 * Math.min(countOfTheWord, count.get(reversedWord));253Please respect copyright.ＰＥＮＡＮＡEBlJE4c2TK
}253Please respect copyright.ＰＥＮＡＮＡRSFPb1f2E4
}253Please respect copyright.ＰＥＮＡＮＡ1EUkU6c0dz
}253Please respect copyright.ＰＥＮＡＮＡcAtlLgcDoW
if (central) {253Please respect copyright.ＰＥＮＡＮＡiUdxOFf9tK
answer++;253Please respect copyright.ＰＥＮＡＮＡxjfR8WMHlX
}253Please respect copyright.ＰＥＮＡＮＡRHQTSo0YoE
return 2 * answer;253Please respect copyright.ＰＥＮＡＮＡGoG0jdNJJ2
}253Please respect copyright.ＰＥＮＡＮＡGY0LCtJolx
}
2: A Two-Dimensional Array Approach
class Solution {253Please respect copyright.ＰＥＮＡＮＡgeMtn6cWKh
public int longestPalindrome(String[] words) {253Please respect copyright.ＰＥＮＡＮＡlrN8I8aJFn
final int alphabetSize = 26;253Please respect copyright.ＰＥＮＡＮＡqqWM2Z1hXb
int[][] count = new int[alphabetSize][alphabetSize];253Please respect copyright.ＰＥＮＡＮＡfimvWqiKHT
// Count the number of occurrences of each word using a two-dimensional array. 253Please respect copyright.ＰＥＮＡＮＡGdWlwlfoNp
for (String word : words) {253Please respect copyright.ＰＥＮＡＮＡpx2TF874Cv
count[word.charAt(0) - 'a'][word.charAt(1) - 'a']++;253Please respect copyright.ＰＥＮＡＮＡcl2PHvmdl4
}253Please respect copyright.ＰＥＮＡＮＡAysAkarKcN
// The answer will denote the number of words in the final string and the boolean variable central will denote whether we have a central word253Please respect copyright.ＰＥＮＡＮＡLyXD7YY163
int answer = 0;253Please respect copyright.ＰＥＮＡＮＡ8mG4P46RPX
boolean central = false;253Please respect copyright.ＰＥＮＡＮＡUMqUfLG2A4
for (int i = 0; i < alphabetSize; i++) {253Please respect copyright.ＰＥＮＡＮＡLuCY261P0z
if (count[i][i] % 2 == 0) {253Please respect copyright.ＰＥＮＡＮＡ8uYuBc6wXJ
answer += count[i][i];253Please respect copyright.ＰＥＮＡＮＡ3fIbC08JTI
} else {253Please respect copyright.ＰＥＮＡＮＡt69dPhQ6nv
answer += count[i][i] - 1;253Please respect copyright.ＰＥＮＡＮＡUpHpQtMQp6
central = true;253Please respect copyright.ＰＥＮＡＮＡHMPOzXwWy7
}253Please respect copyright.ＰＥＮＡＮＡShrvF0Yo4t
for (int j = i + 1; j < alphabetSize; j++) {253Please respect copyright.ＰＥＮＡＮＡ3leCmS7FAz
answer += 2 * Math.min(count[i][j], count[j][i]);253Please respect copyright.ＰＥＮＡＮＡujDogcm6Vv
}253Please respect copyright.ＰＥＮＡＮＡur5wD5Qcs3
}253Please respect copyright.ＰＥＮＡＮＡUfjHD6sNuj
if (central) {253Please respect copyright.ＰＥＮＡＮＡn6hnpYOewK
answer++;253Please respect copyright.ＰＥＮＡＮＡG9S8A1VPMK
}253Please respect copyright.ＰＥＮＡＮＡFZSvDHslRU
return 2 * answer;253Please respect copyright.ＰＥＮＡＮＡhkb3cOCNi0
}253Please respect copyright.ＰＥＮＡＮＡd2qHTuinU4
}
253Please respect copyright.ＰＥＮＡＮＡ50JrHmzXlj
