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 {209Please respect copyright.ＰＥＮＡＮＡU7bS8UWoii
public int longestPalindrome(String[] words) {209Please respect copyright.ＰＥＮＡＮＡI3qtVch3Ot
HashMap<String, Integer> count = new HashMap<String, Integer>();209Please respect copyright.ＰＥＮＡＮＡmHRYGDq0b0
// Count the number of occurrences of each word using a hashmap209Please respect copyright.ＰＥＮＡＮＡ5w4tBNnL4K
for (String word : words) {209Please respect copyright.ＰＥＮＡＮＡ3MMYyyqIIF
Integer countOfTheWord = count.get(word);209Please respect copyright.ＰＥＮＡＮＡlaE2zrkMk9
if (countOfTheWord == null) {209Please respect copyright.ＰＥＮＡＮＡLqeIBzGP9u
count.put(word, 1);209Please respect copyright.ＰＥＮＡＮＡl4B4W2Lsk8
} else {209Please respect copyright.ＰＥＮＡＮＡ4Zbpf6CHzp
count.put(word, countOfTheWord + 1);209Please respect copyright.ＰＥＮＡＮＡssJqm4uVoo
}209Please respect copyright.ＰＥＮＡＮＡoHALISv9zY
}209Please respect copyright.ＰＥＮＡＮＡrb7gQKAYrn
// 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 word209Please respect copyright.ＰＥＮＡＮＡukQvPqOSlg
int answer = 0;209Please respect copyright.ＰＥＮＡＮＡoHZ640uT2C
boolean central = false;209Please respect copyright.ＰＥＮＡＮＡdEuZgZedXx
for (Map.Entry<String, Integer> entry : count.entrySet()) {209Please respect copyright.ＰＥＮＡＮＡ26sAR9949i
String word = entry.getKey();209Please respect copyright.ＰＥＮＡＮＡJAknk9hoOM
int countOfTheWord = entry.getValue();209Please respect copyright.ＰＥＮＡＮＡteiGCJaNtP
// if the word is a palindrome209Please respect copyright.ＰＥＮＡＮＡtzvWEFT06n
if (word.charAt(0) == word.charAt(1)) {209Please respect copyright.ＰＥＮＡＮＡ0EhAJPTORI
if (countOfTheWord % 2 == 0) {209Please respect copyright.ＰＥＮＡＮＡ4In9cc59WO
answer += countOfTheWord;209Please respect copyright.ＰＥＮＡＮＡ14a1l4moHf
} else {209Please respect copyright.ＰＥＮＡＮＡpDD7BNGw40
answer += countOfTheWord - 1;209Please respect copyright.ＰＥＮＡＮＡInv0EUZ3SW
central = true;209Please respect copyright.ＰＥＮＡＮＡ4F5wpgmhlU
}209Please respect copyright.ＰＥＮＡＮＡS0JGKmKkCE
// consider a pair of non-palindrome words such that one is the reverse of another209Please respect copyright.ＰＥＮＡＮＡyKu54IJzIX
} else if (word.charAt(0) < word.charAt(1)) {209Please respect copyright.ＰＥＮＡＮＡ5wQieLDFBD
String reversedWord = "" + word.charAt(1) + word.charAt(0);209Please respect copyright.ＰＥＮＡＮＡ8eLPmAUdZx
if (count.containsKey(reversedWord)) {209Please respect copyright.ＰＥＮＡＮＡi2sg6XtjKt
answer += 2 * Math.min(countOfTheWord, count.get(reversedWord));209Please respect copyright.ＰＥＮＡＮＡostJ80ya0h
}209Please respect copyright.ＰＥＮＡＮＡuhEgbr9cVQ
}209Please respect copyright.ＰＥＮＡＮＡqrMAy9HPfC
}209Please respect copyright.ＰＥＮＡＮＡx6K9o3GqXo
if (central) {209Please respect copyright.ＰＥＮＡＮＡCAuoR0ELRJ
answer++;209Please respect copyright.ＰＥＮＡＮＡ5OIrqRoez2
}209Please respect copyright.ＰＥＮＡＮＡHc2EBnL0UW
return 2 * answer;209Please respect copyright.ＰＥＮＡＮＡWWlggY4mGE
}209Please respect copyright.ＰＥＮＡＮＡbOfavt70Hw
}
2: A Two-Dimensional Array Approach
class Solution {209Please respect copyright.ＰＥＮＡＮＡtQDxPhy0bH
public int longestPalindrome(String[] words) {209Please respect copyright.ＰＥＮＡＮＡmsP1Mnm50r
final int alphabetSize = 26;209Please respect copyright.ＰＥＮＡＮＡaK9mTxmh1x
int[][] count = new int[alphabetSize][alphabetSize];209Please respect copyright.ＰＥＮＡＮＡB0k1Hfy0fo
// Count the number of occurrences of each word using a two-dimensional array. 209Please respect copyright.ＰＥＮＡＮＡGw7tGtCAOp
for (String word : words) {209Please respect copyright.ＰＥＮＡＮＡuHk2GBuQO5
count[word.charAt(0) - 'a'][word.charAt(1) - 'a']++;209Please respect copyright.ＰＥＮＡＮＡ1q3KASfimq
}209Please respect copyright.ＰＥＮＡＮＡHMdZDFE2sV
// The answer will denote the number of words in the final string and the boolean variable central will denote whether we have a central word209Please respect copyright.ＰＥＮＡＮＡSSpvlGFECe
int answer = 0;209Please respect copyright.ＰＥＮＡＮＡGLsrEnGhdN
boolean central = false;209Please respect copyright.ＰＥＮＡＮＡPPIt3Otge3
for (int i = 0; i < alphabetSize; i++) {209Please respect copyright.ＰＥＮＡＮＡEo4hoy7Sea
if (count[i][i] % 2 == 0) {209Please respect copyright.ＰＥＮＡＮＡC6yA5xwWOv
answer += count[i][i];209Please respect copyright.ＰＥＮＡＮＡ83Z9OMyvDX
} else {209Please respect copyright.ＰＥＮＡＮＡx4hWTR4HJd
answer += count[i][i] - 1;209Please respect copyright.ＰＥＮＡＮＡDID9mPE9kL
central = true;209Please respect copyright.ＰＥＮＡＮＡ8BvOnyYRPL
}209Please respect copyright.ＰＥＮＡＮＡNhxw7OuV3S
for (int j = i + 1; j < alphabetSize; j++) {209Please respect copyright.ＰＥＮＡＮＡeVQWrZUwxE
answer += 2 * Math.min(count[i][j], count[j][i]);209Please respect copyright.ＰＥＮＡＮＡUnK2EJtRi6
}209Please respect copyright.ＰＥＮＡＮＡEw3HcnCeZ4
}209Please respect copyright.ＰＥＮＡＮＡvNWfvbjnwx
if (central) {209Please respect copyright.ＰＥＮＡＮＡhmvitt3ARc
answer++;209Please respect copyright.ＰＥＮＡＮＡvBAYMTH5h5
}209Please respect copyright.ＰＥＮＡＮＡONko760ZcW
return 2 * answer;209Please respect copyright.ＰＥＮＡＮＡtbEXbXHceJ
}209Please respect copyright.ＰＥＮＡＮＡLHgvgPu8qM
}
209Please respect copyright.ＰＥＮＡＮＡ1tBhdikEJs
