# 1239. Maximum Length of a Concatenated String with Unique Characters

Question Link is here.

This is a daily challenge problem.

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

At first, my solution was to use Counter to do a brute force. Than I saw that arr can contain at more 16 strings, therefore, brute force will lead to find $2^{16}$ possible answers. This kind of time complxity is unacceptable. So I need to come up with another solution.

The final solution is kind like dp but not dp. Plus, we need to use bit wise operations. Since the problem requires us to find the Longest subsequence with Unique chars, therefore, each char will only appear once in the result subsequence. And there are only 26 chars, so we can use a 26bit mask to count the appearance of each char. And we store the mask of each string, and match the longest solution.

class Solution:
    def maxLength(self, arr: List[str]) -> int:
        ans = 0
        dp = [0]
        for s in arr:
            mask = 0
            for ch in s:
                idx = ord(ch) - ord("a")
                if ((mask >> idx) & 1):
                    mask = 0
                    break
                mask |= 1 << idx
            if mask == 0: #duplicates appeard in the same string
                continue
            #iterate through previous masks
            n = len(dp)
            for i in range(n):
                m = dp[i]
                if (m & mask) == 0: #check if duplicates appears
                    dp.append(m | mask) #generate a new mask
                    ans = max(ans, bin(m | mask).count("1"))
        return ans

This solution has Time complexity of $O(n^2)$. And the space complexity of $O(n^2)$