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 {273Please respect copyright.ＰＥＮＡＮＡDmV69fUCBF
public int longestPalindrome(String[] words) {273Please respect copyright.ＰＥＮＡＮＡTdzs5PKzRc
HashMap<String, Integer> count = new HashMap<String, Integer>();273Please respect copyright.ＰＥＮＡＮＡhdyceUiuWZ
// Count the number of occurrences of each word using a hashmap273Please respect copyright.ＰＥＮＡＮＡYVd0JBvEj7
for (String word : words) {273Please respect copyright.ＰＥＮＡＮＡa1IgHQ5RF7
Integer countOfTheWord = count.get(word);273Please respect copyright.ＰＥＮＡＮＡmRU1L68mWJ
if (countOfTheWord == null) {273Please respect copyright.ＰＥＮＡＮＡQwGSt8oBzX
count.put(word, 1);273Please respect copyright.ＰＥＮＡＮＡgV380LCRXs
} else {273Please respect copyright.ＰＥＮＡＮＡ4Ek9GYOkuo
count.put(word, countOfTheWord + 1);273Please respect copyright.ＰＥＮＡＮＡaDzJyAZ7WL
}273Please respect copyright.ＰＥＮＡＮＡFHrnndB4d2
}273Please respect copyright.ＰＥＮＡＮＡuL91nOQ33D
// 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 word273Please respect copyright.ＰＥＮＡＮＡQb1vVIAzsH
int answer = 0;273Please respect copyright.ＰＥＮＡＮＡyziZ54RlNq
boolean central = false;273Please respect copyright.ＰＥＮＡＮＡbGXrdWDgyN
for (Map.Entry<String, Integer> entry : count.entrySet()) {273Please respect copyright.ＰＥＮＡＮＡPANZlnICh6
String word = entry.getKey();273Please respect copyright.ＰＥＮＡＮＡGIxKWFdadT
int countOfTheWord = entry.getValue();273Please respect copyright.ＰＥＮＡＮＡjymr1L6vYK
// if the word is a palindrome273Please respect copyright.ＰＥＮＡＮＡJ4DFnq7aMm
if (word.charAt(0) == word.charAt(1)) {273Please respect copyright.ＰＥＮＡＮＡMw6dK6vpKD
if (countOfTheWord % 2 == 0) {273Please respect copyright.ＰＥＮＡＮＡ7h1Ejb1WQt
answer += countOfTheWord;273Please respect copyright.ＰＥＮＡＮＡ5RgQ4JjTRG
} else {273Please respect copyright.ＰＥＮＡＮＡL9uwo71rVy
answer += countOfTheWord - 1;273Please respect copyright.ＰＥＮＡＮＡMLEpqfbebT
central = true;273Please respect copyright.ＰＥＮＡＮＡtWUMMeqvfH
}273Please respect copyright.ＰＥＮＡＮＡwiHqXcgouq
// consider a pair of non-palindrome words such that one is the reverse of another273Please respect copyright.ＰＥＮＡＮＡSIqw85Ex6x
} else if (word.charAt(0) < word.charAt(1)) {273Please respect copyright.ＰＥＮＡＮＡhcUwQrmbwu
String reversedWord = "" + word.charAt(1) + word.charAt(0);273Please respect copyright.ＰＥＮＡＮＡjPs05IKHb5
if (count.containsKey(reversedWord)) {273Please respect copyright.ＰＥＮＡＮＡgxghy0ZWsc
answer += 2 * Math.min(countOfTheWord, count.get(reversedWord));273Please respect copyright.ＰＥＮＡＮＡI8onGEcRbc
}273Please respect copyright.ＰＥＮＡＮＡtMPFEVQ8Ya
}273Please respect copyright.ＰＥＮＡＮＡ4UIz6TAcd1
}273Please respect copyright.ＰＥＮＡＮＡ3HF9LcHRo1
if (central) {273Please respect copyright.ＰＥＮＡＮＡJLzWzXvicF
answer++;273Please respect copyright.ＰＥＮＡＮＡlbDBk2DkcG
}273Please respect copyright.ＰＥＮＡＮＡlfNAJMBlZw
return 2 * answer;273Please respect copyright.ＰＥＮＡＮＡGSEwZ3a7TX
}273Please respect copyright.ＰＥＮＡＮＡZyY4GkTGco
}
2: A Two-Dimensional Array Approach
class Solution {273Please respect copyright.ＰＥＮＡＮＡ4sLgY9NDOs
public int longestPalindrome(String[] words) {273Please respect copyright.ＰＥＮＡＮＡ2Lb1U00MAI
final int alphabetSize = 26;273Please respect copyright.ＰＥＮＡＮＡxir7ZkFSY4
int[][] count = new int[alphabetSize][alphabetSize];273Please respect copyright.ＰＥＮＡＮＡ09BRyBKOUV
// Count the number of occurrences of each word using a two-dimensional array. 273Please respect copyright.ＰＥＮＡＮＡAkKox3HcGq
for (String word : words) {273Please respect copyright.ＰＥＮＡＮＡwmAlbq2568
count[word.charAt(0) - 'a'][word.charAt(1) - 'a']++;273Please respect copyright.ＰＥＮＡＮＡWnOdLqUm6R
}273Please respect copyright.ＰＥＮＡＮＡao0qlBYO8t
// The answer will denote the number of words in the final string and the boolean variable central will denote whether we have a central word273Please respect copyright.ＰＥＮＡＮＡ2jyfX49z9u
int answer = 0;273Please respect copyright.ＰＥＮＡＮＡCjkZtpmye9
boolean central = false;273Please respect copyright.ＰＥＮＡＮＡMdyCyrEpcs
for (int i = 0; i < alphabetSize; i++) {273Please respect copyright.ＰＥＮＡＮＡzJ9EpEqHGC
if (count[i][i] % 2 == 0) {273Please respect copyright.ＰＥＮＡＮＡj6ZequNYXp
answer += count[i][i];273Please respect copyright.ＰＥＮＡＮＡQIBR5e489K
} else {273Please respect copyright.ＰＥＮＡＮＡ1gbpX4qqMq
answer += count[i][i] - 1;273Please respect copyright.ＰＥＮＡＮＡKMu4WrhEDr
central = true;273Please respect copyright.ＰＥＮＡＮＡ2JZApWLlud
}273Please respect copyright.ＰＥＮＡＮＡscWZ6Au1eH
for (int j = i + 1; j < alphabetSize; j++) {273Please respect copyright.ＰＥＮＡＮＡNtH7rO75sh
answer += 2 * Math.min(count[i][j], count[j][i]);273Please respect copyright.ＰＥＮＡＮＡ6kJotVWPrD
}273Please respect copyright.ＰＥＮＡＮＡYOIv9gTOhY
}273Please respect copyright.ＰＥＮＡＮＡFeUhZf9flj
if (central) {273Please respect copyright.ＰＥＮＡＮＡKLQUD1eNMh
answer++;273Please respect copyright.ＰＥＮＡＮＡqS0U5wjqg5
}273Please respect copyright.ＰＥＮＡＮＡis1IcsKEwX
return 2 * answer;273Please respect copyright.ＰＥＮＡＮＡwj3e8TLB2Y
}273Please respect copyright.ＰＥＮＡＮＡvFaRQEuj0F
}
273Please respect copyright.ＰＥＮＡＮＡvmPb7JG0jW
