Maximum Length of a Concatenated String with Unique Characters | Simple C++
We can write a simple recursive procedure to find all the possible concatatenation. At the end of it, we can check if it has all unique characters, and update t
We can write a simple recursive procedure to find all the possible concatatenation. At the end of it, we can check if it has all unique characters, and update the maximum length.\n\n\n```\nclass Solution {\npublic:\n    int m = 0;\n    vector<string> arr;\n    \n    int countUnique(string& s){\n        vector<int> freq(26, 0);\n        for(auto c:s){\n            freq[c-\'a\']++;\n        }\n        \n        for(int i=0; i<26; i++){\n            if (freq[i]>1)\n                return -1;\n        }\n        \n        return s.size();\n    }\n    \n    \n    void concat(string base, int i){\n\t    if (base.size()>26){\n\t\t\treturn;              // since the size is greater than 26, all the characters cannot be unique\n        }\n        if (i==arr.size()){\n            m = max(m, countUnique(base));\n            return;            \n        }\n        concat(base, i+1);\n        concat(base+arr[i], i+1);\n    }\n    \n    int maxLength(vector<string>& arr) {\n        this->arr = arr;\n        concat("", 0);\n        return m;\n    }\n};\n```
['Depth-First Search', 'Recursion']