C++ || bit-manipulation || fast (0ms) || clean code
Time permitting I\'ll write up some other solutions for this problem as well, e.g. backtracking would be a common approach to take.\n\n# Approach 1: bitmasking 
Time permitting I\'ll write up some other solutions for this problem as well, e.g. backtracking would be a common approach to take.\n\n# Approach 1: bitmasking and generating valid subsets (0ms)\n\nWe are turn the input array into bitmasks. Each character ```\'a\' ... \'z\'``` gets it\'s own bit. With that we can quickly check with ```and``` if there is a conflict and then expand the match with ```or```. Once we have bitmasks for each element in ```arr``` we are expanding the set of possible solutions and then just look for the largest one.\n\n```cpp\n    static int maxLength(const vector<string>& arr) {\n        // Turn |arr| into bitmasks.\n        vector<int> bms;\n        bms.reserve(arr.size());\n        for (const string& a : arr) {\n            const int m = bitmask(a);\n            if (m != -1) bms.push_back(m);\n        }\n        \n        // Expand the bitmasks if there is no conflict.\n        vector<int> as;\n        for (int bm : bms) {\n            int as_size = as.size();\n            for (int i = 0; i < as_size; ++i)\n                if (!(as[i] & bm)) as.push_back(as[i] | bm);\n            as.push_back(bm);\n        }\n        \n        // Look for the bitmask with the most bits set.\n        int ans = 0;\n        for (int a : as) ans = max(ans, __builtin_popcount(a));\n        return ans;\n    }\n    \n    // Turns |a| into a bitmask for each character present.\n    //   Returns -1 if the characters are not unique.\n    static int bitmask(const string& a) {\n        int ans = 0;\n        for (char ch : a) {\n            const int mask = 1 << (ch - \'a\');\n            if (ans & mask) return -1;\n            ans |= mask;\n        }\n        return ans;\n    }\n```\n\nPicking up an idea from @stanislav-iablokov\'s solution to make the conversion into a bitmask shorter, we end up this:\n\n```cpp\n    static int maxLength(const vector<string>& arr) {\n        // Turn |arr| into bitmasks.\n        vector<int> bms;\n        bms.reserve(arr.size());\n        for (const string& a : arr) {\n            int m = 0;\n            for (char ch : a) m |= 1 << (ch - \'a\');\n            // Are all the characters in |a| unique?\n            if (__builtin_popcount(m) == size(a))\n                bms.push_back(m);\n        }\n        \n        // Expand the bitmasks if there is no conflict.\n        vector<int> as;\n        for (int bm : bms) {\n            int as_size = as.size();\n            for (int i = 0; i < as_size; ++i)\n                if (!(as[i] & bm)) as.push_back(as[i] | bm);\n            as.push_back(bm);\n        }\n        \n        // Look for the bitmask with the most bits set.\n        int ans = 0;\n        for (int a : as) ans = max(ans, __builtin_popcount(a));\n        return ans;\n    }\n```\n\nOther thing I like about @stanislav-iablokov\'s solution is how it handles iterating over the existing part of all combinations while expanding it, instead of:\n\n```cpp\n            int as_size = as.size();\n            for (int i = 0; i < as_size; ++i)\n                if (!(as[i] & bm)) as.push_back(as[i] | bm);\n```\n\nIt does:\n\n```cpp\n            for (int i = size(as) - 1; i >= 0; --i)\n                if (!(as[i] & bm)) as.push_back(as[i] | bm);\n```\n\nIt avoids the temporary variable and the order in which we look at the elements doens\'t matter anyway.\n\nTODO(heder): We could consider an early exit if ```__builtin_popcount(x) == 26```, as we can not improve further.\n\n**Complexity Analsysis**\nIf $$n$$ is the size of ```arr``` then the \n  * Time complexity is $$O(2^n)$$ as we potentially creating the full powerset of ```arr```, and the same is true for the\n  * Space complexity which is also $$O(2^n)$$.\n\n_As always: Feedback, questions, and comments are welcome. Leaving an up-vote sparks joy! :)_\n\n**p.s. Join us on the [LeetCode The Hard Way Discord Server](https://discord.gg/hFUyVyWy2E)!**
['Bit Manipulation', 'C']