239. Maximum Length of a Concatenated String with Unique Characters Medium
Maximum Length of a Concatenated String with Unique Characters\n\nThis repository contains a C++ solution to find the maximum length of a string that can be for
# Maximum Length of a Concatenated String with Unique Characters\n\nThis repository contains a C++ solution to find the maximum length of a string that can be formed by concatenating non-duplicate strings from a given vector of strings.\n\n## Approach\n\nThe approach employed in this solution involves recursive exploration of all possible combinations of strings from the input vector `arr`. The primary steps of the approach are as follows:\n\n1. Define a recursive function `solve` that takes three parameters:\n   - `arr`: The vector of strings.\n   - `i`: The index of the string in `arr` that we are currently looking at.\n   - `mask`: A bitmask that represents the characters that have been added to the current string. If the 0-th bit in the mask is set, it means that "a" has been added to the current string.\n\n2. In the `solve` function, check for base cases:\n   - If the index `i` exceeds the size of the input vector `arr`, return 0.\n\n3. Skip concatenating the current string (`arr[i]`) and recursively call `solve` with the next index `i+1` and the same `mask`. This is done to calculate the maximum length without including the current string.\n\n4. Use a bitmask `mask` to keep track of characters that have been added to the current string. Check whether any character in `arr[i]` is present in the current string by using bitwise operations. If any existing character\'s bit is set, return the result without adding `arr[i]` to the current string.\n\n5. Maintain a character mask `curMask` to prevent concatenation if `arr[i]` itself has duplicate characters. After checking for duplicate characters, update the `mask` to include all the bits set in `curMask` to indicate that these characters are part of the current string.\n\n6. Make a recursive call to `solve` with the updated `mask` and the length of `arr[i]` added to the current result.\n\n7. The `maxLength` function serves as the entry point, initializing the `solve` function with the input vector `arr`, starting at index 0, and with an initial `mask` of 0.\n\n## Intuition\n\nThe intuition behind this approach is to explore all possible combinations of strings from the input vector `arr` while keeping track of characters that have been added to the current string using a bitmask. By avoiding concatenation when duplicate characters are encountered and considering both scenarios (concatenation and skipping) for each string, the code identifies the maximum length of a unique character string that can be formed.\n\n## Complexity Analysis\n\n- Time Complexity: The code explores all possible combinations of strings from the vector `arr`, resulting in a worst-case time complexity of O(2^n), where \'n\' is the number of strings in the input vector `arr`. Dynamic programming techniques could be applied to improve the time complexity.\n- Space Complexity: The space complexity is O(n), where \'n\' is the number of characters in the input vector `arr`. This space is used for the recursion call stack and the `mask` and `curMask` variables.\n\n## Usage\n\nTo find the maximum length of a string that can be formed by concatenating non-duplicate strings from a vector of strings, use the `maxLength` function by providing your input vector `arr`.\n\n\n\n\n# Code\n```\nclass Solution {\npublic:\n    \n    int solve(vector<string> &arr, int i, int mask) {\n        int n = arr.size();\n        if (i >= n){\n            return 0;\n        }\n\n        int curRes = solve(arr, i+1, mask);\n\t\tint curMask = 0;\n        for (char &c: arr[i]) {\n            if (mask & (1 << (c - \'a\'))){\n                return curRes;\n            }\n            \n            if (curMask & (1 << (c - \'a\'))){\n                return curRes;\n            }\n            \n            curMask |= (1 << (c - \'a\'));\n        }\n        mask |= curMask;\n        curRes = max(curRes, (int) arr[i].length() + solve(arr, i+1, mask));\n        return curRes;\n    }\n    \n    int maxLength(vector<string>& arr) {\n        return solve(arr, 0, 0);\n    }\n};\n```
['Backtracking', 'Bit Manipulation', 'C++']