2131: Longest-Palindrome-by-Concatenating-Two-Letter-Words
Medium
Basically, realise that there exist 2 cases for two letter words:
Now, when we iterate through words, we can
check:
Note, the duplicateCount exists to check how many
spare pairs of the same letters exist (since, if
there exists an even number of these pairs, it
makes more sense to pair them up, rather than use one as the
center piece)
For example, if we have 2 copies of aa with other
letters, it makes sense to have aaaa paired up rather
than just use one aa as the center of the
palindrome.
Code:
class Solution {
public:
int longestPalindrome(vector<string>& words) {
int pair = 0;
int duplicateCount = 0;
unordered_map<string, int> mp;
for (string &word : words) {
if (mp[word] > 0) {
pair += 1;
--mp[word];
if (word[0] == word[1]) {
--duplicateCount;
}
} else {
reverse(word.begin(), word.end());
++mp[word];
if (word[0] == word[1]) {
++duplicateCount;
}
}
}
return 4*pair + 2*(duplicateCount > 0);
}
};