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 {303Please respect copyright.ＰＥＮＡＮＡGJv0Dmwhqr
public int longestPalindrome(String[] words) {303Please respect copyright.ＰＥＮＡＮＡak3fFiauKf
HashMap<String, Integer> count = new HashMap<String, Integer>();303Please respect copyright.ＰＥＮＡＮＡDJkhVwdWwS
// Count the number of occurrences of each word using a hashmap303Please respect copyright.ＰＥＮＡＮＡ2LMpUjTHX9
for (String word : words) {303Please respect copyright.ＰＥＮＡＮＡtAvZYQsPeF
Integer countOfTheWord = count.get(word);303Please respect copyright.ＰＥＮＡＮＡv41zROYsJn
if (countOfTheWord == null) {303Please respect copyright.ＰＥＮＡＮＡxINWpSPi2e
count.put(word, 1);303Please respect copyright.ＰＥＮＡＮＡcLC8QBioBS
} else {303Please respect copyright.ＰＥＮＡＮＡeUkVxaqpeG
count.put(word, countOfTheWord + 1);303Please respect copyright.ＰＥＮＡＮＡOYu1GT2E7J
}303Please respect copyright.ＰＥＮＡＮＡaLXk5TqmzC
}303Please respect copyright.ＰＥＮＡＮＡvxXFu3gkiA
// 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 word303Please respect copyright.ＰＥＮＡＮＡapSyrxZ0PG
int answer = 0;303Please respect copyright.ＰＥＮＡＮＡnihq1yQZD3
boolean central = false;303Please respect copyright.ＰＥＮＡＮＡwfCeaATo6p
for (Map.Entry<String, Integer> entry : count.entrySet()) {303Please respect copyright.ＰＥＮＡＮＡkXtRV75BPy
String word = entry.getKey();303Please respect copyright.ＰＥＮＡＮＡXwWerAMSjV
int countOfTheWord = entry.getValue();303Please respect copyright.ＰＥＮＡＮＡiJ9G3ax9EK
// if the word is a palindrome303Please respect copyright.ＰＥＮＡＮＡzmW0aampVC
if (word.charAt(0) == word.charAt(1)) {303Please respect copyright.ＰＥＮＡＮＡBXe7il7ruP
if (countOfTheWord % 2 == 0) {303Please respect copyright.ＰＥＮＡＮＡbmrvcxtohO
answer += countOfTheWord;303Please respect copyright.ＰＥＮＡＮＡCK3HutD9Rg
} else {303Please respect copyright.ＰＥＮＡＮＡwEfM9sQOa3
answer += countOfTheWord - 1;303Please respect copyright.ＰＥＮＡＮＡMJVW5T34cJ
central = true;303Please respect copyright.ＰＥＮＡＮＡLsyLIgBHNC
}303Please respect copyright.ＰＥＮＡＮＡik51xzjkB6
// consider a pair of non-palindrome words such that one is the reverse of another303Please respect copyright.ＰＥＮＡＮＡUgiGtPgbLN
} else if (word.charAt(0) < word.charAt(1)) {303Please respect copyright.ＰＥＮＡＮＡ0sUe2wvaIh
String reversedWord = "" + word.charAt(1) + word.charAt(0);303Please respect copyright.ＰＥＮＡＮＡxS5VQaZ8lx
if (count.containsKey(reversedWord)) {303Please respect copyright.ＰＥＮＡＮＡ02lkPQZoNp
answer += 2 * Math.min(countOfTheWord, count.get(reversedWord));303Please respect copyright.ＰＥＮＡＮＡ54iKtk28ss
}303Please respect copyright.ＰＥＮＡＮＡqbE3EKZq44
}303Please respect copyright.ＰＥＮＡＮＡx01Y9k9u0z
}303Please respect copyright.ＰＥＮＡＮＡRHqGG4NX7R
if (central) {303Please respect copyright.ＰＥＮＡＮＡDGL7nhvza5
answer++;303Please respect copyright.ＰＥＮＡＮＡUR964UyiwB
}303Please respect copyright.ＰＥＮＡＮＡl1cE8LPPMJ
return 2 * answer;303Please respect copyright.ＰＥＮＡＮＡIGD0mQ0yV9
}303Please respect copyright.ＰＥＮＡＮＡxUBnw04YGv
}
2: A Two-Dimensional Array Approach
class Solution {303Please respect copyright.ＰＥＮＡＮＡrRHkj5APK9
public int longestPalindrome(String[] words) {303Please respect copyright.ＰＥＮＡＮＡf3i9kFZlZ1
final int alphabetSize = 26;303Please respect copyright.ＰＥＮＡＮＡuHexZHNQfW
int[][] count = new int[alphabetSize][alphabetSize];303Please respect copyright.ＰＥＮＡＮＡFVwMVBopsA
// Count the number of occurrences of each word using a two-dimensional array. 303Please respect copyright.ＰＥＮＡＮＡKsHMHYqFwH
for (String word : words) {303Please respect copyright.ＰＥＮＡＮＡ5mwImwR4C5
count[word.charAt(0) - 'a'][word.charAt(1) - 'a']++;303Please respect copyright.ＰＥＮＡＮＡDtPcLPdRM0
}303Please respect copyright.ＰＥＮＡＮＡOTsgT4LY02
// The answer will denote the number of words in the final string and the boolean variable central will denote whether we have a central word303Please respect copyright.ＰＥＮＡＮＡJ4nR5ZRCvu
int answer = 0;303Please respect copyright.ＰＥＮＡＮＡ1Nsgd4Dq2O
boolean central = false;303Please respect copyright.ＰＥＮＡＮＡ2dXj8tSkNh
for (int i = 0; i < alphabetSize; i++) {303Please respect copyright.ＰＥＮＡＮＡUCueX7M0hS
if (count[i][i] % 2 == 0) {303Please respect copyright.ＰＥＮＡＮＡguYJyLt3nU
answer += count[i][i];303Please respect copyright.ＰＥＮＡＮＡXmfRdZzo89
} else {303Please respect copyright.ＰＥＮＡＮＡ8INYunSGur
answer += count[i][i] - 1;303Please respect copyright.ＰＥＮＡＮＡTMXKWRS4Zn
central = true;303Please respect copyright.ＰＥＮＡＮＡ1QONa6W4Q5
}303Please respect copyright.ＰＥＮＡＮＡ0VrIxzyATx
for (int j = i + 1; j < alphabetSize; j++) {303Please respect copyright.ＰＥＮＡＮＡvwC6aW769X
answer += 2 * Math.min(count[i][j], count[j][i]);303Please respect copyright.ＰＥＮＡＮＡtb1pXySyib
}303Please respect copyright.ＰＥＮＡＮＡupFeR98JTu
}303Please respect copyright.ＰＥＮＡＮＡBKUWBWghyb
if (central) {303Please respect copyright.ＰＥＮＡＮＡIFhx7YJqZW
answer++;303Please respect copyright.ＰＥＮＡＮＡ9JEhuCZDdK
}303Please respect copyright.ＰＥＮＡＮＡkMO2BIfOI8
return 2 * answer;303Please respect copyright.ＰＥＮＡＮＡHaegO6Xxlb
}303Please respect copyright.ＰＥＮＡＮＡcVGa3YGtkY
}
303Please respect copyright.ＰＥＮＡＮＡdDGcGRde9U
→ Request update
and then Add to home screen.