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 {74Please respect copyright.ＰＥＮＡＮＡjkh2AVPaFl
public int longestPalindrome(String[] words) {74Please respect copyright.ＰＥＮＡＮＡsVuqOB5Mhh
HashMap<String, Integer> count = new HashMap<String, Integer>();74Please respect copyright.ＰＥＮＡＮＡGUyzCdi5X6
// Count the number of occurrences of each word using a hashmap74Please respect copyright.ＰＥＮＡＮＡljU6z0tWy0
for (String word : words) {74Please respect copyright.ＰＥＮＡＮＡuBIqRLVdPM
Integer countOfTheWord = count.get(word);74Please respect copyright.ＰＥＮＡＮＡDB9SnUZDog
if (countOfTheWord == null) {74Please respect copyright.ＰＥＮＡＮＡRclK9ozJ4c
count.put(word, 1);74Please respect copyright.ＰＥＮＡＮＡLKVXNM4LZE
} else {74Please respect copyright.ＰＥＮＡＮＡ17f9tfyQKo
count.put(word, countOfTheWord + 1);74Please respect copyright.ＰＥＮＡＮＡAcCYCIA5dP
}74Please respect copyright.ＰＥＮＡＮＡPB9VBQNnB7
}74Please respect copyright.ＰＥＮＡＮＡI5ljI9kCOG
// 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 word74Please respect copyright.ＰＥＮＡＮＡSPSp7CBROh
int answer = 0;74Please respect copyright.ＰＥＮＡＮＡvp7CtZT0uJ
boolean central = false;74Please respect copyright.ＰＥＮＡＮＡp5jnRtUYmm
for (Map.Entry<String, Integer> entry : count.entrySet()) {74Please respect copyright.ＰＥＮＡＮＡw9VOO54Zz8
String word = entry.getKey();74Please respect copyright.ＰＥＮＡＮＡC8Ah7m1Y1a
int countOfTheWord = entry.getValue();74Please respect copyright.ＰＥＮＡＮＡWw25TWCLkl
// if the word is a palindrome74Please respect copyright.ＰＥＮＡＮＡnYlM1CeA3o
if (word.charAt(0) == word.charAt(1)) {74Please respect copyright.ＰＥＮＡＮＡnsb9xc9oYB
if (countOfTheWord % 2 == 0) {74Please respect copyright.ＰＥＮＡＮＡtozjDmGScF
answer += countOfTheWord;74Please respect copyright.ＰＥＮＡＮＡLIqu88DTti
} else {74Please respect copyright.ＰＥＮＡＮＡPUxnT2l5Rz
answer += countOfTheWord - 1;74Please respect copyright.ＰＥＮＡＮＡMgdxl6l2Um
central = true;74Please respect copyright.ＰＥＮＡＮＡcBbzlYSpqa
}74Please respect copyright.ＰＥＮＡＮＡ2jTkntMpwK
// consider a pair of non-palindrome words such that one is the reverse of another74Please respect copyright.ＰＥＮＡＮＡS5d6zm1hHM
} else if (word.charAt(0) < word.charAt(1)) {74Please respect copyright.ＰＥＮＡＮＡ7ditpgbTXy
String reversedWord = "" + word.charAt(1) + word.charAt(0);74Please respect copyright.ＰＥＮＡＮＡWC9LSAz3O3
if (count.containsKey(reversedWord)) {74Please respect copyright.ＰＥＮＡＮＡXLJG6HKHcD
answer += 2 * Math.min(countOfTheWord, count.get(reversedWord));74Please respect copyright.ＰＥＮＡＮＡLAAC86YTDd
}74Please respect copyright.ＰＥＮＡＮＡcZ9Cq5THY5
}74Please respect copyright.ＰＥＮＡＮＡXi0TY23wrq
}74Please respect copyright.ＰＥＮＡＮＡ7i5uQSkGw6
if (central) {74Please respect copyright.ＰＥＮＡＮＡPJ3Tc42700
answer++;74Please respect copyright.ＰＥＮＡＮＡMXoGlLzArp
}74Please respect copyright.ＰＥＮＡＮＡhLZKdS8Px5
return 2 * answer;74Please respect copyright.ＰＥＮＡＮＡ0cLT2CiBY3
}74Please respect copyright.ＰＥＮＡＮＡFUG7Pro66U
}
2: A Two-Dimensional Array Approach
class Solution {74Please respect copyright.ＰＥＮＡＮＡHML5X2M2X9
public int longestPalindrome(String[] words) {74Please respect copyright.ＰＥＮＡＮＡ0jDUVtVOM5
final int alphabetSize = 26;74Please respect copyright.ＰＥＮＡＮＡOTdAIo7vJL
int[][] count = new int[alphabetSize][alphabetSize];74Please respect copyright.ＰＥＮＡＮＡHJLAA4iKcL
// Count the number of occurrences of each word using a two-dimensional array. 74Please respect copyright.ＰＥＮＡＮＡuL7EUnDYDm
for (String word : words) {74Please respect copyright.ＰＥＮＡＮＡR3nFWpLkWp
count[word.charAt(0) - 'a'][word.charAt(1) - 'a']++;74Please respect copyright.ＰＥＮＡＮＡy6vsTgwEWU
}74Please respect copyright.ＰＥＮＡＮＡywdIWtq4wO
// The answer will denote the number of words in the final string and the boolean variable central will denote whether we have a central word74Please respect copyright.ＰＥＮＡＮＡmNAKlpDAW4
int answer = 0;74Please respect copyright.ＰＥＮＡＮＡJhg2lEknkk
boolean central = false;74Please respect copyright.ＰＥＮＡＮＡtFqXGZHRUJ
for (int i = 0; i < alphabetSize; i++) {74Please respect copyright.ＰＥＮＡＮＡi99XU9J7kl
if (count[i][i] % 2 == 0) {74Please respect copyright.ＰＥＮＡＮＡU7fRNQk8p9
answer += count[i][i];74Please respect copyright.ＰＥＮＡＮＡeABAXl43Xq
} else {74Please respect copyright.ＰＥＮＡＮＡlsqIBCCKVC
answer += count[i][i] - 1;74Please respect copyright.ＰＥＮＡＮＡITcJuVTqgC
central = true;74Please respect copyright.ＰＥＮＡＮＡ6GV0X2u53l
}74Please respect copyright.ＰＥＮＡＮＡjOv0kN4THR
for (int j = i + 1; j < alphabetSize; j++) {74Please respect copyright.ＰＥＮＡＮＡjGlw9ll3cf
answer += 2 * Math.min(count[i][j], count[j][i]);74Please respect copyright.ＰＥＮＡＮＡAG2u0OSU29
}74Please respect copyright.ＰＥＮＡＮＡKMrqt5oQ8N
}74Please respect copyright.ＰＥＮＡＮＡodThI1iysZ
if (central) {74Please respect copyright.ＰＥＮＡＮＡb9aRJB2o8Y
answer++;74Please respect copyright.ＰＥＮＡＮＡEn46TCLIsZ
}74Please respect copyright.ＰＥＮＡＮＡfybayITZ71
return 2 * answer;74Please respect copyright.ＰＥＮＡＮＡ627728b9uA
}74Please respect copyright.ＰＥＮＡＮＡurJVuChWSs
}
74Please respect copyright.ＰＥＮＡＮＡYyEyEcQtep
and then Add to home screen.