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 {299Please respect copyright.ＰＥＮＡＮＡD08knhwQgC
public int longestPalindrome(String[] words) {299Please respect copyright.ＰＥＮＡＮＡvyqoXFLjFb
HashMap<String, Integer> count = new HashMap<String, Integer>();299Please respect copyright.ＰＥＮＡＮＡhawjCXVkV7
// Count the number of occurrences of each word using a hashmap299Please respect copyright.ＰＥＮＡＮＡriIHaY3QS6
for (String word : words) {299Please respect copyright.ＰＥＮＡＮＡu38rKi3CYg
Integer countOfTheWord = count.get(word);299Please respect copyright.ＰＥＮＡＮＡDX83sYOjKk
if (countOfTheWord == null) {299Please respect copyright.ＰＥＮＡＮＡPpmLYxeOUa
count.put(word, 1);299Please respect copyright.ＰＥＮＡＮＡ1aAFutG0XS
} else {299Please respect copyright.ＰＥＮＡＮＡk6mUVZYiBl
count.put(word, countOfTheWord + 1);299Please respect copyright.ＰＥＮＡＮＡqSWqnz9KQ3
}299Please respect copyright.ＰＥＮＡＮＡk6cVLIFDPc
}299Please respect copyright.ＰＥＮＡＮＡTyBRdB6sAn
// 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 word299Please respect copyright.ＰＥＮＡＮＡrFzMoBUxqJ
int answer = 0;299Please respect copyright.ＰＥＮＡＮＡRzQhN1WhGR
boolean central = false;299Please respect copyright.ＰＥＮＡＮＡEjzSFrMSkE
for (Map.Entry<String, Integer> entry : count.entrySet()) {299Please respect copyright.ＰＥＮＡＮＡufrPTRMBVM
String word = entry.getKey();299Please respect copyright.ＰＥＮＡＮＡRRyb3cRD8X
int countOfTheWord = entry.getValue();299Please respect copyright.ＰＥＮＡＮＡ73YjkfehLK
// if the word is a palindrome299Please respect copyright.ＰＥＮＡＮＡuwnebbAqCG
if (word.charAt(0) == word.charAt(1)) {299Please respect copyright.ＰＥＮＡＮＡgYhwlhXNfe
if (countOfTheWord % 2 == 0) {299Please respect copyright.ＰＥＮＡＮＡJFfDFQS3hc
answer += countOfTheWord;299Please respect copyright.ＰＥＮＡＮＡvQoppl0abq
} else {299Please respect copyright.ＰＥＮＡＮＡBEUHXxHXJ3
answer += countOfTheWord - 1;299Please respect copyright.ＰＥＮＡＮＡZ8sqTlKnJT
central = true;299Please respect copyright.ＰＥＮＡＮＡVzQOBkkkf6
}299Please respect copyright.ＰＥＮＡＮＡ4p8H4n2l6g
// consider a pair of non-palindrome words such that one is the reverse of another299Please respect copyright.ＰＥＮＡＮＡPUTR9rnmQf
} else if (word.charAt(0) < word.charAt(1)) {299Please respect copyright.ＰＥＮＡＮＡ2At0EQbrQj
String reversedWord = "" + word.charAt(1) + word.charAt(0);299Please respect copyright.ＰＥＮＡＮＡ2titvk19CR
if (count.containsKey(reversedWord)) {299Please respect copyright.ＰＥＮＡＮＡDQqRvytaSC
answer += 2 * Math.min(countOfTheWord, count.get(reversedWord));299Please respect copyright.ＰＥＮＡＮＡkimMRZXguI
}299Please respect copyright.ＰＥＮＡＮＡMkrV3NnIYv
}299Please respect copyright.ＰＥＮＡＮＡ5uGTORiOMH
}299Please respect copyright.ＰＥＮＡＮＡ06Y56MkzaG
if (central) {299Please respect copyright.ＰＥＮＡＮＡt0SmStHgV8
answer++;299Please respect copyright.ＰＥＮＡＮＡ4GT7M9uUNn
}299Please respect copyright.ＰＥＮＡＮＡPYeBOR32W3
return 2 * answer;299Please respect copyright.ＰＥＮＡＮＡ7wWEsaIcFo
}299Please respect copyright.ＰＥＮＡＮＡ5Jat8ET63q
}
2: A Two-Dimensional Array Approach
class Solution {299Please respect copyright.ＰＥＮＡＮＡWHlo98J3L3
public int longestPalindrome(String[] words) {299Please respect copyright.ＰＥＮＡＮＡxOdF0NKc45
final int alphabetSize = 26;299Please respect copyright.ＰＥＮＡＮＡfSrJ9zxXI7
int[][] count = new int[alphabetSize][alphabetSize];299Please respect copyright.ＰＥＮＡＮＡMnlRqX5fLn
// Count the number of occurrences of each word using a two-dimensional array. 299Please respect copyright.ＰＥＮＡＮＡmrmZMTwId7
for (String word : words) {299Please respect copyright.ＰＥＮＡＮＡfrgsX9FPmD
count[word.charAt(0) - 'a'][word.charAt(1) - 'a']++;299Please respect copyright.ＰＥＮＡＮＡktTYox895b
}299Please respect copyright.ＰＥＮＡＮＡ7mvb1imgk5
// The answer will denote the number of words in the final string and the boolean variable central will denote whether we have a central word299Please respect copyright.ＰＥＮＡＮＡxLkw6NTtwk
int answer = 0;299Please respect copyright.ＰＥＮＡＮＡ7ACcRGNers
boolean central = false;299Please respect copyright.ＰＥＮＡＮＡtZPXkInakH
for (int i = 0; i < alphabetSize; i++) {299Please respect copyright.ＰＥＮＡＮＡGWtPMarvAc
if (count[i][i] % 2 == 0) {299Please respect copyright.ＰＥＮＡＮＡ1dUmJK36yJ
answer += count[i][i];299Please respect copyright.ＰＥＮＡＮＡ01ctwWQORK
} else {299Please respect copyright.ＰＥＮＡＮＡalh5UBNNDH
answer += count[i][i] - 1;299Please respect copyright.ＰＥＮＡＮＡrxDygRpeZJ
central = true;299Please respect copyright.ＰＥＮＡＮＡsJxaAms2Xl
}299Please respect copyright.ＰＥＮＡＮＡqtpPWJRDMI
for (int j = i + 1; j < alphabetSize; j++) {299Please respect copyright.ＰＥＮＡＮＡL7QB7PtUU6
answer += 2 * Math.min(count[i][j], count[j][i]);299Please respect copyright.ＰＥＮＡＮＡcyJdnCKi6i
}299Please respect copyright.ＰＥＮＡＮＡyvbGDrHv7z
}299Please respect copyright.ＰＥＮＡＮＡCGLd8M3vEc
if (central) {299Please respect copyright.ＰＥＮＡＮＡNj4YPFk7Fq
answer++;299Please respect copyright.ＰＥＮＡＮＡLDrwdD2djf
}299Please respect copyright.ＰＥＮＡＮＡXt3sKs4mgM
return 2 * answer;299Please respect copyright.ＰＥＮＡＮＡGeRNoI35uX
}299Please respect copyright.ＰＥＮＡＮＡRc8gN6o1xv
}
299Please respect copyright.ＰＥＮＡＮＡpoXG8jQsjY
→ Request update
and then Add to home screen.