C++ recursion with bitset||0ms beats 100%
Intuition\n Describe your first thoughts on how to solve this problem. \nSince 1 <= arr.length <= 16, use recursion to try all combinations, there are at most o
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nSince `1 <= arr.length <= 16`, use recursion to try all combinations, there are at most only $2^{16}$ combinations .\n\nFor fast comparing whether both strings having common characters, bitset is in use. Such computations are fast because they are bitwise operations.\n\nDP version with bitMask is also provided. Note that there are $n\\times 2^n$ different states.\n# Approach\n<!-- Describe your approach to solving the problem. -->\n[Spoken in Mandarin. Please turn on the English subtitles if necessary]\n[https://youtu.be/tdR2Dq4oeqU?si=RdU_QnRXI_Cvvo2E](https://youtu.be/tdR2Dq4oeqU?si=RdU_QnRXI_Cvvo2E)\nThe edge case `["aa","bb"]` makes me to rebuild the following functions:\n1. `bitset<27> charSet(string& s)`: if `s` has duplicate characters, return `(1<<27)-1`. Input string s, output is equivalently the char set represented by a 27-bit `bitset`\n2. `bool hasCommon(bitset<27> f1, bitset<27> f2)`: Use bitwise operation `&` to check whether these two char sets have any same character.\n3. `bitset<27> charUnion(bitset<27>& f1, bitset<27>& f2) `: Use bitwise operation `|` to operate equivalently the set union operation of these 2 char sets.\n4.  `int f(int i, bitset<27> s)`: Use the recursive function to try all combinations. \n\nThis uses recursion to try all combinations. I don\'t want to use unordered_set, unordered_map. After encountering the  annoying edge cases  it is clear that I misunderstood the meaning of the problem. After correction, use bitset which is very efficient. This way, the code beats 100%  of users with C++ in speed.\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# C++ Code||0ms beats 100%\n```\n#pragma GCC optimize("O3", "unroll-loops")\nclass Solution {\npublic:\n    bitset<27>no= (1<<27)-1; // Set all 27 bits to 1. for edge case ["aa","bb"]\n    bitset<27> charSet(string& s){\n        bitset<27> f(0);\n        for(char c: s){\n            if (f[c-\'a\'+1]==1) return no;\n            f[c-\'a\'+1]=1;\n        }    \n        return f;\n    }\n    bool hasCommon(bitset<27> f1, bitset<27> f2){\n        return (f1 & f2).any();\n    }\n\n    bitset<27> charUnion(bitset<27>& f1, bitset<27>& f2){\n        return f1 | f2;\n    }\n\n    int n;\n    vector<string> arr;\n    vector<bitset<27>> char_a;\n\n    int f(int i, bitset<27> s){\n        if (i == n) \n            return s.count(); //return the count of set bits in the bitset\n    \n        if (char_a[i]==no) return f(i+1, s);\n        int has_ai=0;\n        // Check if including the current string is possible\n        if (!hasCommon(s, char_a[i])){\n        //    cout<<i<<": "<<arr[i]<<endl;\n            // Include the current string and update the bitset\n            bitset<27> newSet = charUnion(s, char_a[i]);\n            has_ai=f(i+1, newSet);\n        } \n        int no_ai = f(i+1, s);\n        return max(has_ai, no_ai);\n    }\n\n    int maxLength(vector<string>& arr) {\n        n=arr.size();\n        this->arr=arr;\n        char_a.resize(n);\n        for (int i=0; i<n; i++)\n            char_a[i]=charSet(arr[i]);\n\n        bitset<27> emptySet(0);\n        return f(0, emptySet); \n    }\n};\n\nauto init = []()\n{ \n    ios::sync_with_stdio(0);\n    cin.tie(0);\n    cout.tie(0);\n    return \'c\';\n}();\n```\n# C++ short version of 1st code\n```\n#pragma GCC optimize("O3", "unroll-loops")\nclass Solution {\npublic:\n    static constexpr bitset<27> no= (1<<27)-1; // Set all 27 bits to 1. for edge case ["aa","bb"]\n    int n;\n    vector<string> arr;\n    vector<bitset<27>> char_a;\n\n    int f(int i, bitset<27> s){\n        if (i == n) \n            return s.count(); //return the count of set bits in the bitset\n    \n        if (char_a[i]==no) return f(i+1, s);\n        int has_ai=0;\n        // Check if including the current string is possible\n        if (!(s & char_a[i]).any()){\n            has_ai=f(i+1, (s|char_a[i]));\n        } \n        int no_ai = f(i+1, s);\n        return max(has_ai, no_ai);\n    }\n\n    int maxLength(vector<string>& arr) {\n        n=arr.size();\n        this->arr=arr;\n        char_a.resize(n);\n        for (int i=0; i<n; i++)\n            for(char c: arr[i]){\n                if ( char_a[i][c-\'a\'+1]==1){\n                    char_a[i]=no;\n                    break;\n                }\n                char_a[i][c-\'a\'+1]=1;\n            }   \n        bitset<27> emptySet(0);\n        return f(0, emptySet); \n    }\n};\n\n```\n# revised C++ DP version with bitMask using bitset\n```\n#pragma GCC optimize("O3", "unroll-loops")\nclass Solution {\npublic:\n    bitset<27>no= (1<<27)-1; // Set all 27 bits to 1. for edge case ["aa","bb"]\n    bitset<27> charSet(string& s){\n        bitset<27> f(0);\n        for(char c: s){\n            if (f[c-\'a\'+1]==1) return no;\n            f[c-\'a\'+1]=1;\n        }    \n        return f;\n    }\n    bool hasCommon(bitset<27>& f1, bitset<27>& f2){\n        return (f1 & f2).any();\n    }\n\n    bitset<27> charUnion(bitset<27>& f1, bitset<27>& f2){\n        return f1 | f2;\n    }\n\n    int n;\n    vector<vector<int>> dp;\n    vector<string> arr;\n    vector<bitset<27>> char_a;\n\n    int f(int i, bitset<27> s, bitset<16>& bitMask){\n        if (i == n) \n            return s.count(); //return the count of set bits in the bitset\n        if (dp[i][bitMask.to_ulong()]!=-1) return dp[i][bitMask.to_ulong()];\n        if (char_a[i]==no) return dp[i][bitMask.to_ulong()]=f(i+1, s, bitMask);\n        int has_ai=0;\n        // Check if including the current string is possible\n        if (!hasCommon(s, char_a[i])){\n        //    cout<<i<<": "<<arr[i]<<endl;\n            // Include the current string and update the bitset\n            bitset<27> newSet = charUnion(s, char_a[i]);\n            bitMask[i]=1;\n            has_ai=f(i+1, newSet, bitMask);\n        }\n        bitMask[i]=0; \n        int no_ai = f(i+1, s, bitMask);\n        return dp[i][bitMask.to_ulong()]=max(has_ai, no_ai);\n    }\n\n    int maxLength(vector<string>& arr) {\n        n=arr.size();\n        this->arr=arr;\n        char_a.resize(n);\n        for (int i=0; i<n; i++)\n            char_a[i]=charSet(arr[i]);\n        dp.assign(n, vector<int>(1<<n, -1));\n        bitset<27> emptySet(0);\n        bitset<16> bitMask(0);\n        return f(0, emptySet, bitMask); \n    }\n}\n```
['Dynamic Programming', 'Backtracking', 'Bit Manipulation', 'Recursion', 'Bitmask', 'C++']