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 {71Please respect copyright.PENANAxnblrNfk2j
public int longestPalindrome(String[] words) {71Please respect copyright.PENANA97vyHEZm4K
HashMap<String, Integer> count = new HashMap<String, Integer>();71Please respect copyright.PENANA5AABizho8t
// Count the number of occurrences of each word using a hashmap71Please respect copyright.PENANAyeNU4jCPA2
for (String word : words) {71Please respect copyright.PENANAno6RrjhmFf
Integer countOfTheWord = count.get(word);71Please respect copyright.PENANAAFAUZ7mrKy
if (countOfTheWord == null) {71Please respect copyright.PENANAJeMfB5JD7n
count.put(word, 1);71Please respect copyright.PENANAlL2KsAJtEs
} else {71Please respect copyright.PENANAekaDrh8uSa
count.put(word, countOfTheWord + 1);71Please respect copyright.PENANAAKTOrxUUUI
}71Please respect copyright.PENANAErBFqS50CC
}71Please respect copyright.PENANAYr5oRMLoNc
// 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 word71Please respect copyright.PENANAwfzidBuamH
int answer = 0;71Please respect copyright.PENANAUcuc6KEi8b
boolean central = false;71Please respect copyright.PENANAztYFTMmOBk
for (Map.Entry<String, Integer> entry : count.entrySet()) {71Please respect copyright.PENANA4dD7pvb2RU
String word = entry.getKey();71Please respect copyright.PENANAgpk1jo23JF
int countOfTheWord = entry.getValue();71Please respect copyright.PENANAaUHjcxW5Dw
// if the word is a palindrome71Please respect copyright.PENANApTn06gwMdc
if (word.charAt(0) == word.charAt(1)) {71Please respect copyright.PENANAljg0lmZfAZ
if (countOfTheWord % 2 == 0) {71Please respect copyright.PENANArXHAcuNwUp
answer += countOfTheWord;71Please respect copyright.PENANA3MjgMJQl1c
} else {71Please respect copyright.PENANAZmVmT436Dr
answer += countOfTheWord - 1;71Please respect copyright.PENANAlQvQVFbFbi
central = true;71Please respect copyright.PENANAw0qdTPvkzc
}71Please respect copyright.PENANAqOIRaYmltf
// consider a pair of non-palindrome words such that one is the reverse of another71Please respect copyright.PENANAtx1N5jCBkV
} else if (word.charAt(0) < word.charAt(1)) {71Please respect copyright.PENANA3NmCRHsWZ7
String reversedWord = "" + word.charAt(1) + word.charAt(0);71Please respect copyright.PENANAgEBmOeyys4
if (count.containsKey(reversedWord)) {71Please respect copyright.PENANA787i7ngx6q
answer += 2 * Math.min(countOfTheWord, count.get(reversedWord));71Please respect copyright.PENANAg4xYt2PKGT
}71Please respect copyright.PENANAcJZourSpZG
}71Please respect copyright.PENANAGWkCrF6JoQ
}71Please respect copyright.PENANAdU9WQYcClG
if (central) {71Please respect copyright.PENANAx0LRc4OHJk
answer++;71Please respect copyright.PENANAmJMebov3Qw
}71Please respect copyright.PENANA3vTqThAP4a
return 2 * answer;71Please respect copyright.PENANAKJASkG9KuZ
}71Please respect copyright.PENANAvrR3zZG1Ta
}
2: A Two-Dimensional Array Approach
class Solution {71Please respect copyright.PENANA4tNpQrWdBP
public int longestPalindrome(String[] words) {71Please respect copyright.PENANAU5by6GJ2dP
final int alphabetSize = 26;71Please respect copyright.PENANAZsQuroZPMO
int[][] count = new int[alphabetSize][alphabetSize];71Please respect copyright.PENANA4kpvt7BQkk
// Count the number of occurrences of each word using a two-dimensional array. 71Please respect copyright.PENANAlWOLEoL3Ea
for (String word : words) {71Please respect copyright.PENANA2M4KjtoOCx
count[word.charAt(0) - 'a'][word.charAt(1) - 'a']++;71Please respect copyright.PENANAbQ1iN4yz0y
}71Please respect copyright.PENANAobsxcNFSyP
// The answer will denote the number of words in the final string and the boolean variable central will denote whether we have a central word71Please respect copyright.PENANAChj52cRyor
int answer = 0;71Please respect copyright.PENANALjDNVxDAbH
boolean central = false;71Please respect copyright.PENANAhY3E1OOctv
for (int i = 0; i < alphabetSize; i++) {71Please respect copyright.PENANADXAZTw6kRK
if (count[i][i] % 2 == 0) {71Please respect copyright.PENANAGFOxy03EfL
answer += count[i][i];71Please respect copyright.PENANABZD6YbVqms
} else {71Please respect copyright.PENANAJUFteQcBWQ
answer += count[i][i] - 1;71Please respect copyright.PENANAF2SFa4wcjw
central = true;71Please respect copyright.PENANANhPaRfA4DE
}71Please respect copyright.PENANArHBXQFYdPs
for (int j = i + 1; j < alphabetSize; j++) {71Please respect copyright.PENANAFxUjP9Q6b6
answer += 2 * Math.min(count[i][j], count[j][i]);71Please respect copyright.PENANA4W5zRlgs7X
}71Please respect copyright.PENANAAUBsvfek5v
}71Please respect copyright.PENANAdCKhNHMbM1
if (central) {71Please respect copyright.PENANANU6k1x1Whg
answer++;71Please respect copyright.PENANAd30XIGLwLK
}71Please respect copyright.PENANA5aK25xiy3A
return 2 * answer;71Please respect copyright.PENANA2au9Rc7O2G
}71Please respect copyright.PENANABKmtWDyT9L
}
71Please respect copyright.PENANAmhHlq6TGIB