🔥🔥Bitmasking >>  Recursion
Intuition\nThe idea is that we can try all possible combinations of arr by using Bitmasking\nThere are total 2^n bitmasking states: 0..000, 0..001, 0..010, ...,
# Intuition\nThe idea is that we can try all possible combinations of arr by using Bitmasking\nThere are total 2^n bitmasking states: 0..000, 0..001, 0..010, ..., 1..111\n\n# Approach\nLet comb represent one of the combination ,then the ith bit of comb = 1 means there exists arr[i] in our combination\nFor each combination ,we check if it can form a valid string? If we can form then we update the maximum length so far\n\n\n# Complexity\n- Time complexity:\n$$O(2^n * n))$$ where n is the length of the array arr\n\n- Space complexity:\n$$O(1)$$\n\n# Code\n```\nclass Solution {\npublic:\n    int maxLength(vector<string>& arr) {\n        int n=arr.size();\n        int mask=(1ll<<n),ans=0;\n        for(int comb=0;comb<mask;comb++) {\n            int charMask=0,res=0;\n            bool inValid=false;\n            for(int i=0;i<n;++i) {\n                if(!(1 & (comb>>i))) continue;\n                for(char &ch :arr[i]) {\n                    int idx=ch-\'a\';\n                    if((charMask>>idx) & 1) {\n                        inValid=true;\n                        break;\n                    }\n                    charMask|=(1ll<<idx);\n                    res++;\n                }\n                if(inValid) break;\n            }\n            if(!inValid) ans=max(ans,res);\n        }\n        return ans;\n    }\n};\n```\n\nHope you found this helpful\nIf so please do Upvote it\nHappy Coding!!\n\n![leetcode.png](https://assets.leetcode.com/users/images/7a98ada3-fb9b-4413-8538-92fe790f4577_1701070150.1852815.png)
['Array', 'String', 'Backtracking', 'Bit Manipulation', 'Bitmask', 'C++']