[C++] Frequency Mapping (HashMap vs. Array vs. Array + Bitmask) Solutions Explained, 176ms, 166.8MB
Really nice problem, of the kind that forces you to think more than to just remember some esoteric algorithm or pattern.\n\nWe know that we can have two scenari
Really nice problem, of the kind that forces you to think more than to just remember some esoteric algorithm or pattern.\n\nWe know that we can have two scenarios:\n* using an even amount of words, in whatever order and in pairs, so that we use all the symmmetrical ones (ie: `"ab"` would form a valid palindrome with `"ba"`, in whatever order we will put them;\n* using an odd amount of words, with a scenario similar to the previous, and just putting a single self-symmetrical word in the middle (ie: if we had an even number of `"cc"`s, we could build any kind of palindrome with it at the center, like `"abccbaccabccba"` or `"ccbaabccbaabcc"` or any other combination of those pairs which is symmetrical - and notice that we would still be using any even number of them to the left and right of the centre of the word).\n\nNow, the first part really makes me think that we need first of all to know how many occurrences of each word we will get and that is a handbook definition of a frequency map!\n\nFor the second part, we will try with some extra bit of logic.\n\nNow, with that in mind, let\'s get ourselves a few support variables:\n* `res` is going to be our accumulator variable, initially set to `0`;\n* `freq` is where we will store the frequency of each word;\n* `sym` is a set where we will store all the unique symmetrical words we will parse;\n* `rev` is a temporary string where we will build our reversed strings as we go.\n\nWe can then start parsing each string `s` in `words and:\n* we will create `rev` as the reverse of `s`l\n* we will check if we still have some unused amounts of `rev` in store and, in case:\n\t* use it, decreasing the frequency of `rev` by `1`;\n\t* add the usage of `2` words to `res`;\n* otherwise, we will:\n\t* store `s` as available, increasing its frequency in `freq` by `1`;\n\t* check if `s` is symmmetrical and in case add it to `sym`.\n\nWe will then check if we actually still have a single word `sym` in store whose frequency is not `0` and, if so, we will further increase `res` by `1`, meaning we employed it as the centre of a palindrome.\n\nFinally, we can just `return` double the value of `res` (since each element we used was made by two characters and that is what we need to return).\n\nThe code:\n\n```cpp\nclass Solution {\npublic:\n    int longestPalindrome(vector<string>& words) {\n        // support variables\n        int res = 0;\n        unordered_map<string, int> freq;\n        unordered_set<string> sym;\n        string rev;\n        for (auto &s: words) {\n            // creating the reverse of the current string\n            rev = "";\n            rev += s[1];\n            rev += s[0];\n            // checking if we had a reverse already\n            if (freq[rev] > 0) {\n                freq[rev]--;\n                res += 2;\n            }\n            else {\n                freq[s]++;\n                // storing symmetrical words\n                if (s[0] == s[1]) sym.insert(s);\n            }\n        }\n        // checking if we can have a central word\n        for (auto s: sym) {\n            if (freq[s]) {\n                res ++;\n                break;\n            }\n        }\n        return (res << 1);\n    }\n};\n```\n\nBut, wait a moment - storing all the unique symmetrical values and looking up for them when we would need only ones seems a bit needlessly expensive \uD83E\uDD14 ... What if instead we stored only their amount?\n\nYes, that would make us save a bit of memory and run faster, as it did (the memory saved was anyway close to negligible, to my surprise, even with the micro-optimisation of better queries for `freq`):\n\n```cpp\nclass Solution {\npublic:\n    int longestPalindrome(vector<string>& words) {\n        // support variables\n        int res = 0, sym = 0;\n        unordered_map<string, int> freq;\n        string rev;\n        for (auto &s: words) {\n            // creating the reverse of the current string\n            rev = "";\n            rev += s[1];\n            rev += s[0];\n            // checking if we had a reverse already\n            auto pos = freq.find(rev);\n            if (pos != end(freq) && pos->second > 0) {\n                freq[rev]--;\n                res += 2;\n                // removing one symmetrical word\n                if (s[0] == s[1]) sym--;\n            }\n            else {\n                freq[s]++;\n                // storing symmetrical words\n                if (s[0] == s[1]) sym++;\n            }\n        }\n        // checking if we can have a central word\n        res += bool(sym);\n        return (res << 1);\n    }\n};\n```\n\nCan we do even better? Well, whenever we can avoid hashing and can instead opt for a simpler way of finding elements, we definitely can; in this case  we know that we can have at most `26 * 26` different combinations of `2` characters, so it is something we can definitely work with.\n\nInstead of hashing we will get the index of each possible string and its reverse with `getPos`, with the added benefit of also having to only compare two integers directly to find symmetrical words (ie: words whose index is equal to the one of their reverse).\n\nThe code works just better, with also a bit of memory saved while at it:\n\n```cpp\nclass Solution {\n    pair<int, int> getPos(string &s) {\n        int s0 = s[0] - \'a\', s1 = s[1] - \'a\';\n        // returning position of s and of its reverse\n        return {s0 * 26 + s1, s1 * 26 + s0};\n    }\npublic:\n    int longestPalindrome(vector<string>& words) {\n        // support variables\n        int res = 0, sym = 0, freq[676] = {};\n        for (auto &s: words) {\n            // checking if we had a reverse already\n            auto pos = getPos(s);\n            if (freq[pos.second] > 0) {\n                freq[pos.second]--;\n                res += 2;\n                // removing one symmetrical word\n                if (pos.first == pos.second) sym--;\n            }\n            else {\n                freq[pos.first]++;\n                // storing symmetrical words\n                if (pos.first == pos.second) sym++;\n            }\n        }\n        // checking if we can have a central word\n        res += bool(sym);\n        return (res << 1);\n    }\n};\n```\n\nBut what if we further optimise, shifting the the value of the first character by `5` bits left (since numbers up to `25` can take at max `5` bits) and then add the value of the second? Binary shifts are way cheaper than multiplying.\n\nSure, we will have some more unused cells in our array-acting-as-a-hashmap, but if we do the math, we will see that is only `26 * 26 == 676` cells vs `(25 << 5) + 26 == 826` - a net different of `150` cells: we can live with that and it really goes faster!\n\nThe final code:\n\n```cpp\nclass Solution {\n    pair<int, int> getPos(string &s) {\n        int s0 = s[0] - \'a\', s1 = s[1] - \'a\';\n        // returning position of s and of its reverse\n        return {(s0 << 5) + s1, (s1 << 5) + s0};\n    }\npublic:\n    int longestPalindrome(vector<string>& words) {\n        // support variables\n        int res = 0, sym = 0, freq[826] = {};\n        for (auto &s: words) {\n            // checking if we had a reverse already\n            auto pos = getPos(s);\n            if (freq[pos.second] > 0) {\n                freq[pos.second]--;\n                res += 2;\n                // removing one symmetrical word\n                if (pos.first == pos.second) sym--;\n            }\n            else {\n                freq[pos.first]++;\n                // storing symmetrical words\n                if (pos.first == pos.second) sym++;\n            }\n        }\n        // checking if we can have a central word\n        res += bool(sym);\n        return (res << 1);\n    }\n};\n```\n\nThe brag:\n![image](https://assets.leetcode.com/users/images/521654a2-7082-4842-8929-daaa99f2710d_1641752011.9171124.png)\n
['Bit Manipulation', 'C', 'Bitmask', 'C++']