Maximum Length Of A Concatenated String With Unique Characters - Leetcode Solution

Problem Statement:

Given an array of strings arr. String s is a concatenation of a sub-sequence of arr which have unique characters.

Return the maximum possible length of s.

Solution:

To solve the Maximum Length Of A Concatenated String With Unique Characters problem, we need to follow the following steps:

1. We will start by creating all the possible sub-sequences of the given array of strings. We can do this by using a recursive approach.
2. Then, we will check whether each sub-sequence has unique characters or not. If a sub-sequence has duplicate characters, we will discard it.
3. Finally, we will find the sub-sequence with the maximum length of unique characters.

Here's the complete code implementation for the above approach:

class Solution {
public:
    int maxLength(vector<string>& arr) {
        int ans = 0;
        vector<string> subSeq;
        generateSubSequence(arr, 0, "", subSeq);
        for (auto s : subSeq) {
            if (hasDuplicate(s)) continue;
            ans = max(ans, (int)s.size());
        }
        return ans;
    }
    void generateSubSequence(vector<string>& arr, int index, string curr, vector<string>& subSeq) {
        if (index == arr.size()) {
            subSeq.push_back(curr);
            return;
        }
        generateSubSequence(arr, index+1, curr, subSeq);
        generateSubSequence(arr, index+1, curr+arr[index], subSeq);
    }
    bool hasDuplicate(string s) {
        vector<int> freq(26, 0);
        for (auto c : s) {
            if (freq[c-'a'] > 0) return true;  // Duplicate found
            freq[c-'a']++;
        }
        return false;
    }
};

Time Complexity:

The time complexity of this solution is O(2^n * k * k), where n is the length of the input array and k is the length of the longest string in the array. The reason for this time complexity is that we are generating all the possible sub-sequences, which can be at most 2^n, and for each sub-sequence, we are checking whether it has duplicate characters or not, which takes k time.

Space Complexity:

The space complexity of this solution is O(2^n * k), where n is the length of the input array and k is the length of the longest string in the array. The reason for this space complexity is that we are storing all the possible sub-sequences, which can be at most 2^n, and each sub-sequence can have k characters.

1