[C++] Set Vs. Hashing String to Int Vs. Bitmask Hashing, 4ms, 20.5MB
Let\'s start with the simplest approach, which means we will use a hashset (seen) to keep track of already encountered strings.\n\nMore specifically, we will st
Let\'s start with the simplest approach, which means we will use a hashset (`seen`) to keep track of already encountered strings.\n\nMore specifically, we will start declaring:\n* `res` as our usual counter variable, initially set to be `0`;\n* `seen`, our set where we will store what we already saw (or its reverse, in the second version of this solution down below).\n\nFor each `word` in `words`, we will:\n* store the original `word` in `orig`;\n* swap its first and second character;\n* check if we have ever seen the newly reversed `word` in `seen` and, if so, increase `res` by `1`;\n* store `orig` in `seen`.\n\nFinally, we will `return` `res`.\n\n# Complexity\n- Time complexity: $$O(n)$$\n- Space complexity: $$O(n)$$\n\n# Code\n```cpp\nclass Solution {\npublic:\n    int maximumNumberOfStringPairs(vector<string> &words) {\n        // suppor variables\n        int res = 0;\n        unordered_set<string> seen;\n        // parsing words\n        for (string &word: words) {\n            string orig = word;\n            swap(word[0], word[1]);\n            if (seen.find(word) != end(seen)) res++;\n            seen.insert(orig);\n        }\n        return res;\n    }\n};\n```\n\nWe can actually play a bit smarter here and look up for the word itself, then store just the reverse of it, having to use `tmp` all the time:\n\n# Complexity\n- Time complexity: $$O(n)$$\n- Space complexity: $$O(n)$$\n\n# Code\n\n```cpp\nclass Solution {\npublic:\n    int maximumNumberOfStringPairs(vector<string> &words) {\n        // suppor variables\n        int res = 0;\n        unordered_set<string> seen;\n        // parsing words\n        for (string &word: words) {\n            if (seen.find(word) != end(seen)) res++;\n            swap(word[0], word[1]);\n            seen.insert(word);\n        }\n        return res;\n    }\n};\n```\n\nBut we can do better if we just consider that we have an alphabet of only `26` characters, and each word will only be `2` characters - so we can hash each string counting in base `26`, for a grant total of `26 * 26 == 676` cells.\n\nWe can then hash each word into an `int` and do way quicker checks about what we have seen before or not (albeit with potentially higher initialisation costs for `seen` with smaller sets of words).\n\nNotice we might actually optimise a bit more, space-wise, if we consider that strings like `"aa"`, `"bb"`, `"cc"`, etc. have no place being considered and since they appear every `27` positions, proceeding lexicographically, we might adjust our hashing by subtracting its value `/ 27`, but not really worth all the cost to save a handful of bites.\n\n# Complexity\n- Time complexity: $$O(n)$$\n- Space complexity: $$O(1)$$\n\n# Code\n```cpp\nconstexpr int maxRange = 676;\n\nclass Solution {\npublic:\n    int maximumNumberOfStringPairs(vector<string> &words) {\n        // suppor variables\n        int res = 0, tmp;\n        bool seen[maxRange] = {};\n        // parsing words\n        for (string &word: words) {\n            tmp = (word[0] - \'a\') * 26 + word[1] - \'a\';\n            if (seen[tmp]) res++;\n            seen[(word[1] - \'a\') * 26 + word[0] - \'a\'] = true;\n        }\n        return res;\n    }\n};\n```\n\nSame core logic, but hashing getting the value of each character with a bitmask (`\'a\' & 31` is `1`, `\'b\' & 31` is `2`, and so on), using `5` bits for each digits (since they are enough to represent values up to `31`, so fully within our range), which makes `10` bits total or, in other words, `1024` slots in `seen`.\n\nAgain, not a major increment with the small values we are dealing with, but still maybe a tad faster and a lot of fun to handle.\n\n# Complexity\n- Time complexity: $$O(n)$$\n- Space complexity: $$O(1)$$\n\n# Code\n```cpp\nconstexpr int maxRange = 1024, bitmask = 31;\n\nclass Solution {\npublic:\n    int maximumNumberOfStringPairs(vector<string> &words) {\n        // suppor variables\n        int res = 0, tmp;\n        bool seen[maxRange] = {};\n        // parsing words\n        for (string &word: words) {\n            tmp = ((word[0] & bitmask) << 5) + (word[1] & bitmask);\n            if (seen[tmp]) res++;\n            seen[((word[1] & bitmask) << 5) + (word[0] & bitmask)] = true;\n        }\n        return res;\n    }\n};\n```
['String', 'Bit Manipulation', 'Hash Function', 'Bitmask', 'C++']