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 {130Please respect copyright.ＰＥＮＡＮＡ2TIuJGzfBI
public int longestPalindrome(String[] words) {130Please respect copyright.ＰＥＮＡＮＡYDojjAq5vi
HashMap<String, Integer> count = new HashMap<String, Integer>();130Please respect copyright.ＰＥＮＡＮＡokXVfAEfTH
// Count the number of occurrences of each word using a hashmap130Please respect copyright.ＰＥＮＡＮＡWtJx8aY6Ew
for (String word : words) {130Please respect copyright.ＰＥＮＡＮＡ8zs8i7RY3K
Integer countOfTheWord = count.get(word);130Please respect copyright.ＰＥＮＡＮＡlz5jBKK6dY
if (countOfTheWord == null) {130Please respect copyright.ＰＥＮＡＮＡC9zQpK2rJl
count.put(word, 1);130Please respect copyright.ＰＥＮＡＮＡxKygkHZITT
} else {130Please respect copyright.ＰＥＮＡＮＡnJ53k5RGRQ
count.put(word, countOfTheWord + 1);130Please respect copyright.ＰＥＮＡＮＡL3UyZJwwcG
}130Please respect copyright.ＰＥＮＡＮＡVdPdJDWwfk
}130Please respect copyright.ＰＥＮＡＮＡfC73PrNSQ7
// 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 word130Please respect copyright.ＰＥＮＡＮＡzHJ1MmMTWy
int answer = 0;130Please respect copyright.ＰＥＮＡＮＡi7Fx59MplY
boolean central = false;130Please respect copyright.ＰＥＮＡＮＡbD3SHMC82k
for (Map.Entry<String, Integer> entry : count.entrySet()) {130Please respect copyright.ＰＥＮＡＮＡEu86q0Td8v
String word = entry.getKey();130Please respect copyright.ＰＥＮＡＮＡ5l0fxGqUTD
int countOfTheWord = entry.getValue();130Please respect copyright.ＰＥＮＡＮＡmH4CwJwdFX
// if the word is a palindrome130Please respect copyright.ＰＥＮＡＮＡiUFQjuOamS
if (word.charAt(0) == word.charAt(1)) {130Please respect copyright.ＰＥＮＡＮＡnpdlYsJKcT
if (countOfTheWord % 2 == 0) {130Please respect copyright.ＰＥＮＡＮＡqQFlfowVp7
answer += countOfTheWord;130Please respect copyright.ＰＥＮＡＮＡGN4tCGyV0j
} else {130Please respect copyright.ＰＥＮＡＮＡk5MLuNUals
answer += countOfTheWord - 1;130Please respect copyright.ＰＥＮＡＮＡFJ2qLDh8E0
central = true;130Please respect copyright.ＰＥＮＡＮＡNEyQiMOVgF
}130Please respect copyright.ＰＥＮＡＮＡpDLj0UeQeS
// consider a pair of non-palindrome words such that one is the reverse of another130Please respect copyright.ＰＥＮＡＮＡO7kBwTIPNe
} else if (word.charAt(0) < word.charAt(1)) {130Please respect copyright.ＰＥＮＡＮＡMmh9iaAXwD
String reversedWord = "" + word.charAt(1) + word.charAt(0);130Please respect copyright.ＰＥＮＡＮＡ9OKw8Nvs0W
if (count.containsKey(reversedWord)) {130Please respect copyright.ＰＥＮＡＮＡUaER9K8kLK
answer += 2 * Math.min(countOfTheWord, count.get(reversedWord));130Please respect copyright.ＰＥＮＡＮＡfxfwt35Iqp
}130Please respect copyright.ＰＥＮＡＮＡj5inlCRwyF
}130Please respect copyright.ＰＥＮＡＮＡxlCUwbl9PA
}130Please respect copyright.ＰＥＮＡＮＡ5FYb8xSSFW
if (central) {130Please respect copyright.ＰＥＮＡＮＡXFPK3KYO3q
answer++;130Please respect copyright.ＰＥＮＡＮＡq3MLJl24QZ
}130Please respect copyright.ＰＥＮＡＮＡGMCHtRrRyA
return 2 * answer;130Please respect copyright.ＰＥＮＡＮＡ6A0yFJS0zL
}130Please respect copyright.ＰＥＮＡＮＡgVCf0cW80f
}
2: A Two-Dimensional Array Approach
class Solution {130Please respect copyright.ＰＥＮＡＮＡfhiyp8UpNr
public int longestPalindrome(String[] words) {130Please respect copyright.ＰＥＮＡＮＡcTexgWLOCf
final int alphabetSize = 26;130Please respect copyright.ＰＥＮＡＮＡkkTiSjzBlb
int[][] count = new int[alphabetSize][alphabetSize];130Please respect copyright.ＰＥＮＡＮＡWqzZQ8sXUj
// Count the number of occurrences of each word using a two-dimensional array. 130Please respect copyright.ＰＥＮＡＮＡXMcB9ujhqc
for (String word : words) {130Please respect copyright.ＰＥＮＡＮＡSpVBHX3Uta
count[word.charAt(0) - 'a'][word.charAt(1) - 'a']++;130Please respect copyright.ＰＥＮＡＮＡZ4jQT9bTCE
}130Please respect copyright.ＰＥＮＡＮＡiwYtF21Kuh
// The answer will denote the number of words in the final string and the boolean variable central will denote whether we have a central word130Please respect copyright.ＰＥＮＡＮＡvMbj2y7uK4
int answer = 0;130Please respect copyright.ＰＥＮＡＮＡtaqAuVNIrG
boolean central = false;130Please respect copyright.ＰＥＮＡＮＡGtY7MTR6du
for (int i = 0; i < alphabetSize; i++) {130Please respect copyright.ＰＥＮＡＮＡasHkFfqkWp
if (count[i][i] % 2 == 0) {130Please respect copyright.ＰＥＮＡＮＡhTBJO7YlF0
answer += count[i][i];130Please respect copyright.ＰＥＮＡＮＡt6jSOnAx9O
} else {130Please respect copyright.ＰＥＮＡＮＡq4ljVPzamB
answer += count[i][i] - 1;130Please respect copyright.ＰＥＮＡＮＡh5Oc4Vpk4z
central = true;130Please respect copyright.ＰＥＮＡＮＡWIO7uCrhen
}130Please respect copyright.ＰＥＮＡＮＡXYwSM5hnuV
for (int j = i + 1; j < alphabetSize; j++) {130Please respect copyright.ＰＥＮＡＮＡ7GTrmcZMVZ
answer += 2 * Math.min(count[i][j], count[j][i]);130Please respect copyright.ＰＥＮＡＮＡ62E5FxZaxH
}130Please respect copyright.ＰＥＮＡＮＡO3LO3GNgxJ
}130Please respect copyright.ＰＥＮＡＮＡJdUv7Rv2Rj
if (central) {130Please respect copyright.ＰＥＮＡＮＡMnkFgfWd3W
answer++;130Please respect copyright.ＰＥＮＡＮＡuYUFpHB0wn
}130Please respect copyright.ＰＥＮＡＮＡUmISRHX6L1
return 2 * answer;130Please respect copyright.ＰＥＮＡＮＡn6ADBkfyXH
}130Please respect copyright.ＰＥＮＡＮＡ0oYbSy9LxC
}
130Please respect copyright.ＰＥＮＡＮＡaYtzKtooxf
