Maximum Length of a Concatenated String with Unique Characters Leetcode Solution

Problem Statement

The Maximum Length of a Concatenated String with Unique Characters LeetCode Solution – “Maximum Length of a Concatenated String with Unique Characters” says that you’re given an array of strings and you need to choose any subsequence of the given array and concatenate those strings to form the new string that must contain only unique characters. We need to maximize the length of the new string formed by choosing the suitable subsequence.

Note: 1<=arr.length<=16

Example:

Input:  arr = ["un","iq","ue"]

Output: 4

Explanation:

• Given input array has size 3.
• Consider all subsequences of the given array.
• [“”,”ue”,”iq”,”ique”,”un”,”unue”,”uniq”,”unique”] are the subsequences of the given input array.
• We can easily observe that strings at 1,2,3,4,5,7 are valid strings (strings containing only unique characters).
• Hence maximum length among all valid strings is 4.

Input:  arr = ["cha","r","act","ers"]

Output: 6

Explanation:

• The maximum length of valid string that we can have is 6.
• One of the possible subsequence that gives 6 as the valid length is : “cha” + “ers” = “charers”

Approach

Idea:

1. The main idea to solve this problem is to consider all possible subsets of the input array using Bitmasking (since n<=16).
2. Let mask represent the appearance of arr[i], an ith bit of mask = 1 means there exists arr[i] in the subsequence.
3. There is a total of 2^n bitmasking states starting from 0 to (2^n – 1) representing each possible subset that we can have.
4. For each subset of the input array, we check if it can form a valid string?. If it can form, we’ll update the maximum length so far.
5. Note that we’ll check if the subsets chosen to form a valid string by checking the resultant string must contain only distinct characters.

Code

C++ Solution:

class Solution {
public:
    bool NoDuplicate(int& found,string s){
        for(auto& c:s){
            int pos = c-'a';
            if((1<<pos)&found){
                return false;
            }
            found |= (1<<pos);
        }
        return true;
    }
    int maxLength(vector<string>& arr) {
        int ans = 0,n = arr.size();
        for(int mask=0;mask<(1<<n);mask++){
            int len = 0,ok = 1,found = 0;
            for(int i=0;i<n and ok;i++){
                if((1<<i)&mask){
                    if(!NoDuplicate(found,arr[i])){
                        ok = 0;
                    }
                    else{
                        len += arr[i].length();
                    }
                }
            }
            if(ok){
                ans = max(ans,len);
            }
        }
        return ans;
    }
};

Java Solution:

class Solution {
    int found;
    private int NoDuplicate(String s){
        for(int i=0;i<s.length();i++){
            int pos = s.charAt(i)-'a';
            if(((1<<pos)&found)>0){
                return 0;
            }
            found += (1<<pos);
        }
        return 1;
    }
    public int maxLength(List<String> arr) {
        int ans = 0,n = arr.size();
        for(int mask=0;mask<(1<<n);mask++){
            found = 0;
            int len = 0,ok = 1;
            for(int i=0;i<n&&(ok>0);i++){
                if(((1<<i)&mask)>0){
                    if(NoDuplicate(arr.get(i))==0){
                        ok = 0;
                        break;
                    }
                    else{
                        len += arr.get(i).length();
                    }
                }
            }
            if(ok==1){
                ans = Math.max(ans,len);
            }
        }
        return ans;
    }
}

Complexity Analysis for Maximum Length of Concatenated String with Unique Characters Leetcode Solution

Time Complexity

The time complexity of the above code is O(N * 2^N). We’re generating all possible subsets using bit masking hence 2^N factor comes. Also, for each subset, we’re iterating in the entire input array, hence overall complexity if O(N * 2^N).

Space Complexity

The space complexity of the above code is O(1) since we’re using only constant space.

Reference: https://en.wikipedia.org/wiki/Bit_manipulation