Longest Palindrome by Concatenating Two Letter Words

Basically, realise that there exist 2 cases for two letter words:

• a pair of the same letters, e.g. 'aa'
• a pair of different letters, e.g. 'ab'

Now, when we iterate through words, we can check:

• if we have seen the reverse of word before, we can decrement its count in the hashmap and add 1 to the counter
  • then, if they are both made up of the same letters, we can decrement the duplicateCount
• if we have NOT seen the reverse of word before, we can increment its count in the hashmap
  • then, if they are both made up of the same letters, we can increment the duplicateCount

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: O(n * m) where n is the size of words and m is the size of the largest word inside words
• Space: O(n)

time taken

• 11 minutes and 54 seconds
  • it was not a hard question; just trying to see what way is more efficient
  • theoretically existed another way of using a 26x26 matrix to store each pair of strings