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 {230Please respect copyright.ＰＥＮＡＮＡPGFWoJgctZ
public int longestPalindrome(String[] words) {230Please respect copyright.ＰＥＮＡＮＡ4V8yAwfILC
HashMap<String, Integer> count = new HashMap<String, Integer>();230Please respect copyright.ＰＥＮＡＮＡNiQVwchtSi
// Count the number of occurrences of each word using a hashmap230Please respect copyright.ＰＥＮＡＮＡjSf9YWDgUB
for (String word : words) {230Please respect copyright.ＰＥＮＡＮＡnr0ro6Ub0y
Integer countOfTheWord = count.get(word);230Please respect copyright.ＰＥＮＡＮＡIbD5oQOmH1
if (countOfTheWord == null) {230Please respect copyright.ＰＥＮＡＮＡhNif07SDWD
count.put(word, 1);230Please respect copyright.ＰＥＮＡＮＡuhKF2j6VIQ
} else {230Please respect copyright.ＰＥＮＡＮＡZyCZQhCine
count.put(word, countOfTheWord + 1);230Please respect copyright.ＰＥＮＡＮＡI3mwfbakZS
}230Please respect copyright.ＰＥＮＡＮＡfCVItkhH12
}230Please respect copyright.ＰＥＮＡＮＡAKmq4os9FI
// 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 word230Please respect copyright.ＰＥＮＡＮＡMXnOIF1C3p
int answer = 0;230Please respect copyright.ＰＥＮＡＮＡ3l9ggedhak
boolean central = false;230Please respect copyright.ＰＥＮＡＮＡC0NLpYaFGj
for (Map.Entry<String, Integer> entry : count.entrySet()) {230Please respect copyright.ＰＥＮＡＮＡa7HSTxiybZ
String word = entry.getKey();230Please respect copyright.ＰＥＮＡＮＡfsDLDHxMrY
int countOfTheWord = entry.getValue();230Please respect copyright.ＰＥＮＡＮＡA7Zbo4UMVi
// if the word is a palindrome230Please respect copyright.ＰＥＮＡＮＡe9IXSVJK8G
if (word.charAt(0) == word.charAt(1)) {230Please respect copyright.ＰＥＮＡＮＡ4QWF1JAiw6
if (countOfTheWord % 2 == 0) {230Please respect copyright.ＰＥＮＡＮＡopiFJo3Zyc
answer += countOfTheWord;230Please respect copyright.ＰＥＮＡＮＡfuHjdX28rs
} else {230Please respect copyright.ＰＥＮＡＮＡQb0DqO14os
answer += countOfTheWord - 1;230Please respect copyright.ＰＥＮＡＮＡ4fBh1HLGZA
central = true;230Please respect copyright.ＰＥＮＡＮＡpClnza8siP
}230Please respect copyright.ＰＥＮＡＮＡw0GuxjdON4
// consider a pair of non-palindrome words such that one is the reverse of another230Please respect copyright.ＰＥＮＡＮＡaTY4rsW7T2
} else if (word.charAt(0) < word.charAt(1)) {230Please respect copyright.ＰＥＮＡＮＡErO9cAUH1m
String reversedWord = "" + word.charAt(1) + word.charAt(0);230Please respect copyright.ＰＥＮＡＮＡM4oHFXc58W
if (count.containsKey(reversedWord)) {230Please respect copyright.ＰＥＮＡＮＡbLRolEtB0H
answer += 2 * Math.min(countOfTheWord, count.get(reversedWord));230Please respect copyright.ＰＥＮＡＮＡvcy9BqB0AE
}230Please respect copyright.ＰＥＮＡＮＡ0EUvxEmxLh
}230Please respect copyright.ＰＥＮＡＮＡe4lb56rqfm
}230Please respect copyright.ＰＥＮＡＮＡV4I25JyZCd
if (central) {230Please respect copyright.ＰＥＮＡＮＡ2wNc6JNIXl
answer++;230Please respect copyright.ＰＥＮＡＮＡNVreNbCmrG
}230Please respect copyright.ＰＥＮＡＮＡc9x6mWobKi
return 2 * answer;230Please respect copyright.ＰＥＮＡＮＡz7ppo48jI3
}230Please respect copyright.ＰＥＮＡＮＡPIz0SoryOi
}
2: A Two-Dimensional Array Approach
class Solution {230Please respect copyright.ＰＥＮＡＮＡyY5t65INr7
public int longestPalindrome(String[] words) {230Please respect copyright.ＰＥＮＡＮＡsDC7rSgEK6
final int alphabetSize = 26;230Please respect copyright.ＰＥＮＡＮＡYVHF3E9r4U
int[][] count = new int[alphabetSize][alphabetSize];230Please respect copyright.ＰＥＮＡＮＡVNpopZk7F4
// Count the number of occurrences of each word using a two-dimensional array. 230Please respect copyright.ＰＥＮＡＮＡYZAtRVvaVT
for (String word : words) {230Please respect copyright.ＰＥＮＡＮＡqZuoUiCo4y
count[word.charAt(0) - 'a'][word.charAt(1) - 'a']++;230Please respect copyright.ＰＥＮＡＮＡrSEzblnHM4
}230Please respect copyright.ＰＥＮＡＮＡzOuW1HteqD
// The answer will denote the number of words in the final string and the boolean variable central will denote whether we have a central word230Please respect copyright.ＰＥＮＡＮＡ0oT5WnAZ8S
int answer = 0;230Please respect copyright.ＰＥＮＡＮＡ2lSosgIZ7t
boolean central = false;230Please respect copyright.ＰＥＮＡＮＡ9QGsQjyOfh
for (int i = 0; i < alphabetSize; i++) {230Please respect copyright.ＰＥＮＡＮＡ8OdbEUS96o
if (count[i][i] % 2 == 0) {230Please respect copyright.ＰＥＮＡＮＡNtnPkYhmht
answer += count[i][i];230Please respect copyright.ＰＥＮＡＮＡsNrni8p5AK
} else {230Please respect copyright.ＰＥＮＡＮＡ4dz3jIhY0P
answer += count[i][i] - 1;230Please respect copyright.ＰＥＮＡＮＡqAWJ0J6Jqn
central = true;230Please respect copyright.ＰＥＮＡＮＡPS7CmDE3xJ
}230Please respect copyright.ＰＥＮＡＮＡOMoEOFiDAk
for (int j = i + 1; j < alphabetSize; j++) {230Please respect copyright.ＰＥＮＡＮＡnTvXtxYNrM
answer += 2 * Math.min(count[i][j], count[j][i]);230Please respect copyright.ＰＥＮＡＮＡ4zNMAmcLmV
}230Please respect copyright.ＰＥＮＡＮＡbyRTLrsnsa
}230Please respect copyright.ＰＥＮＡＮＡm85Ei6tPri
if (central) {230Please respect copyright.ＰＥＮＡＮＡ5Qn2NlTJgI
answer++;230Please respect copyright.ＰＥＮＡＮＡfsccF73fFg
}230Please respect copyright.ＰＥＮＡＮＡ3p328eCgn8
return 2 * answer;230Please respect copyright.ＰＥＮＡＮＡ8cyWM7vYug
}230Please respect copyright.ＰＥＮＡＮＡ1JXUZr8ZLH
}
230Please respect copyright.ＰＥＮＡＮＡU3RXMJcONy
