2131: Longest-Palindrome-by-Concatenating-Two-Letter-Words
Medium

table of contents

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);
    }
};

complexity

time taken