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 {449Please respect copyright.ＰＥＮＡＮＡJEHYl2g2hl
public int longestPalindrome(String[] words) {449Please respect copyright.ＰＥＮＡＮＡovcvwMitEV
HashMap<String, Integer> count = new HashMap<String, Integer>();449Please respect copyright.ＰＥＮＡＮＡR9GzfNguv7
// Count the number of occurrences of each word using a hashmap449Please respect copyright.ＰＥＮＡＮＡtocJGZqtun
for (String word : words) {449Please respect copyright.ＰＥＮＡＮＡEQCHAvEYbw
Integer countOfTheWord = count.get(word);449Please respect copyright.ＰＥＮＡＮＡ8GWzheYfYo
if (countOfTheWord == null) {449Please respect copyright.ＰＥＮＡＮＡKcaYBAOgvn
count.put(word, 1);449Please respect copyright.ＰＥＮＡＮＡLiqQ0OUcwA
} else {449Please respect copyright.ＰＥＮＡＮＡbO6NCD89sz
count.put(word, countOfTheWord + 1);449Please respect copyright.ＰＥＮＡＮＡhvOZfpGdve
}449Please respect copyright.ＰＥＮＡＮＡS9mAqrOAPG
}449Please respect copyright.ＰＥＮＡＮＡF9cvnBH2O9
// 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 word449Please respect copyright.ＰＥＮＡＮＡCSDVUyrjAK
int answer = 0;449Please respect copyright.ＰＥＮＡＮＡsgDy28UyEb
boolean central = false;449Please respect copyright.ＰＥＮＡＮＡ1gX6snyCwU
for (Map.Entry<String, Integer> entry : count.entrySet()) {449Please respect copyright.ＰＥＮＡＮＡLoRmeQbWgo
String word = entry.getKey();449Please respect copyright.ＰＥＮＡＮＡn3OClw9T1m
int countOfTheWord = entry.getValue();449Please respect copyright.ＰＥＮＡＮＡ7UpvWzp4hl
// if the word is a palindrome449Please respect copyright.ＰＥＮＡＮＡlsAIlThk2A
if (word.charAt(0) == word.charAt(1)) {449Please respect copyright.ＰＥＮＡＮＡF4FXpibVva
if (countOfTheWord % 2 == 0) {449Please respect copyright.ＰＥＮＡＮＡYn7yXsaCht
answer += countOfTheWord;449Please respect copyright.ＰＥＮＡＮＡLjczZjQK6q
} else {449Please respect copyright.ＰＥＮＡＮＡ8XFzML8LKq
answer += countOfTheWord - 1;449Please respect copyright.ＰＥＮＡＮＡrei9Mf9lkC
central = true;449Please respect copyright.ＰＥＮＡＮＡOCP9D6DmX4
}449Please respect copyright.ＰＥＮＡＮＡHTlDZltAEl
// consider a pair of non-palindrome words such that one is the reverse of another449Please respect copyright.ＰＥＮＡＮＡ5wVzYTxbtb
} else if (word.charAt(0) < word.charAt(1)) {449Please respect copyright.ＰＥＮＡＮＡPLnBFkGyXK
String reversedWord = "" + word.charAt(1) + word.charAt(0);449Please respect copyright.ＰＥＮＡＮＡnBaHotWYYD
if (count.containsKey(reversedWord)) {449Please respect copyright.ＰＥＮＡＮＡjQ8jcBPmlJ
answer += 2 * Math.min(countOfTheWord, count.get(reversedWord));449Please respect copyright.ＰＥＮＡＮＡzsxVqMXgva
}449Please respect copyright.ＰＥＮＡＮＡuZpXcHt88C
}449Please respect copyright.ＰＥＮＡＮＡQ3Cd4U0QEh
}449Please respect copyright.ＰＥＮＡＮＡybW2idYrkX
if (central) {449Please respect copyright.ＰＥＮＡＮＡkQ4KOmvd4a
answer++;449Please respect copyright.ＰＥＮＡＮＡvBG6rUWts4
}449Please respect copyright.ＰＥＮＡＮＡENXUjuNxgH
return 2 * answer;449Please respect copyright.ＰＥＮＡＮＡL5QLdmjEXe
}449Please respect copyright.ＰＥＮＡＮＡGMcd94bTCI
}
2: A Two-Dimensional Array Approach
class Solution {449Please respect copyright.ＰＥＮＡＮＡgdO6CIMj8E
public int longestPalindrome(String[] words) {449Please respect copyright.ＰＥＮＡＮＡxw4dv74w7X
final int alphabetSize = 26;449Please respect copyright.ＰＥＮＡＮＡ9NLC54yuck
int[][] count = new int[alphabetSize][alphabetSize];449Please respect copyright.ＰＥＮＡＮＡ8RPGsmvQyG
// Count the number of occurrences of each word using a two-dimensional array. 449Please respect copyright.ＰＥＮＡＮＡkpfn5HhhjE
for (String word : words) {449Please respect copyright.ＰＥＮＡＮＡwrSLkIX2vQ
count[word.charAt(0) - 'a'][word.charAt(1) - 'a']++;449Please respect copyright.ＰＥＮＡＮＡDZmNtCjz7N
}449Please respect copyright.ＰＥＮＡＮＡdRkAcizyn6
// The answer will denote the number of words in the final string and the boolean variable central will denote whether we have a central word449Please respect copyright.ＰＥＮＡＮＡRelcPrXV2t
int answer = 0;449Please respect copyright.ＰＥＮＡＮＡUHKb0QhaSV
boolean central = false;449Please respect copyright.ＰＥＮＡＮＡJhklrdW7Nl
for (int i = 0; i < alphabetSize; i++) {449Please respect copyright.ＰＥＮＡＮＡUzBl1Ngw5B
if (count[i][i] % 2 == 0) {449Please respect copyright.ＰＥＮＡＮＡkFRALdwEBl
answer += count[i][i];449Please respect copyright.ＰＥＮＡＮＡYPhNy1BUmM
} else {449Please respect copyright.ＰＥＮＡＮＡxIqCMn2Vbi
answer += count[i][i] - 1;449Please respect copyright.ＰＥＮＡＮＡzYnMvm4nbS
central = true;449Please respect copyright.ＰＥＮＡＮＡ17Xy7dGBPO
}449Please respect copyright.ＰＥＮＡＮＡh58dSdX8Sw
for (int j = i + 1; j < alphabetSize; j++) {449Please respect copyright.ＰＥＮＡＮＡnsik2Xrifl
answer += 2 * Math.min(count[i][j], count[j][i]);449Please respect copyright.ＰＥＮＡＮＡjKvE0hpHWK
}449Please respect copyright.ＰＥＮＡＮＡ2ImgJi9wai
}449Please respect copyright.ＰＥＮＡＮＡSChwcz8OVG
if (central) {449Please respect copyright.ＰＥＮＡＮＡc81H7S1f2L
answer++;449Please respect copyright.ＰＥＮＡＮＡNq908zsHr0
}449Please respect copyright.ＰＥＮＡＮＡ0yYpGbpE2e
return 2 * answer;449Please respect copyright.ＰＥＮＡＮＡGOLS75uazm
}449Please respect copyright.ＰＥＮＡＮＡM3uz9aqZzw
}
449Please respect copyright.ＰＥＮＡＮＡ5bTPVBwMU2
and then Add to home screen.