C++ | DFS | Bit Masking | O(2^N) | Trick to find duplicate characters with XOR and OR
Observation\nIf two binary representations do not contain any common bit then their XOR should be equal to their OR\n\n\nExample\n10101 and 01010 \nXOR and OR a
*Observation*\n**If two binary representations do not contain any common bit then their XOR should be equal to their OR**\n\n```\nExample\n10101 and 01010 \nXOR and OR are both equal [11111] , say we have 101 and 100 then its clear that XOR !=OR \n```\n\n**CODE**\n```\n    int ans=0;\n    void dfs(string curr,int index,vector<string> &arr,int bit){\n        if(index==arr.size()) { \n            ans=max(ans,(int)curr.length()); return; \n        }\n        dfs(curr,index+1,arr,bit); //we dont include the current string\n        int mask=0;\n        for(auto x:arr[index]) {\n            if((mask&(1<<(x-\'a\')))!=0) return; //checks duplicates within the string like ["aa","xyx"]\n            mask|=1<<(x-\'a\');\n        }\n        if((mask^bit)==(mask|bit)){\n            dfs(curr+arr[index],index+1,arr,mask|bit); //we choose the string \n        }\n    }\n    int maxLength(vector<string>& arr) {\n        dfs("",0,arr,0);\n        return ans;\n    }\n```
['Backtracking', 'Depth-First Search', 'Bitmask']