[C++/Python] Simple Bitmasking - Clean & Concise
Idea\n- The idea is that we try all possible subset of arr by using Bitmasking, same with 78. Subsets.\n- Let mask represent the appearance of arr[i], ith bit o
**Idea**\n- The idea is that we try all possible subset of `arr` by using Bitmasking, same with **[78. Subsets](https://leetcode.com/problems/subsets/)**.\n- Let `mask` represent the appearance of `arr[i]`, ith bit of mask = 1 means there exists `arr[i]`.\n- There are total `2^n` bitmasking states: `0..000`, `0..001`, `0..010`, ..., `1..111`.\n- For each subsets of `arr`, we check if it can form a valid string? If we can form then we update the maximum length so far.\n\n**Python 3**\n```python\nclass Solution:\n    def maxLength(self, arr: List[str]) -> int:\n        n = len(arr)\n        ans = 0\n        for mask in range(1 << n):\n            seen = set()\n            isValid = True\n            strSize = 0\n            for i in range(n):\n                if (mask >> i) & 1 == 0: continue\n                for c in arr[i]:\n                    if c in seen:   # If c is already existed then it\'s invalid subsequence.\n                        isValid = False\n                        break\n                    seen.add(c)  # mark as character `c` is already seen\n                    strSize += 1\n                if not isValid: break  # prune when there is a duplicate\n            if isValid and strSize > ans:\n                ans = strSize\n        return ans\n```\n\n**C++**\n```c++\nclass Solution { // 36 ms, faster than 66.95%\npublic:\n    int maxLength(vector<string>& arr) {\n        int n = arr.size(), allMask = 1 << n, ans = 0;\n        for (int mask = 0; mask < allMask; ++mask) {\n            int strSize = 0;\n            int seen = 0; // the mask to check duplicate chars when forming string\n            bool isValid = true;\n            for (int i = 0; i < n; ++i) {\n                if (((mask >> i) & 1) == 0) continue;\n                for (char c : arr[i]) {\n                    int j = c - \'a\';\n                    if ((seen >> j) & 1) { // If c is already existed then it\'s invalid subsequence.\n                        isValid = false;\n                        break;\n                    }\n                    seen = seen | (1 << j); // mark as character `c` is already seen\n                    strSize += 1;\n                }\n                if (!isValid) break; //  prune when there is a duplicate\n            }\n            if (isValid && strSize > ans) ans = strSize;\n        }\n        return ans;\n    }\n};\n```\n\nComplexity:\n- Time: `O(2^n * (26 + n))`, where `n <= 16` is length of `arr` array.\n\t- There is `2^n` bitmask states.\n\t- There are up to 26 distinct characters we can form.\n- Space: `O(26)`\n\nIf you think this **post is useful**, I\'m happy if you **give a vote**. Any **questions or discussions are welcome!** Thank a lot.
[]