1239

1239. Maximum Length of a Concatenated String with Unique Characters (Medium)

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.

 

Example 1:

Input: arr = ["un","iq","ue"]
Output: 4
Explanation: All possible concatenations are "","un","iq","ue","uniq" and "ique".
Maximum length is 4.

Example 2:

Input: arr = ["cha","r","act","ers"]
Output: 6
Explanation: Possible solutions are "chaers" and "acters".

Example 3:

Input: arr = ["abcdefghijklmnopqrstuvwxyz"]
Output: 26

 

Constraints:

• 1 <= arr.length <= 16
• 1 <= arr[i].length <= 26
• arr[i] contains only lower case English letters.

Companies:
Tesla, Microsoft, DiDi, American Express

Related Topics:
Array, String, Backtracking, Bit Manipulation

Solution 1. Bitmask

// OJ: https://leetcode.com/problems/maximum-length-of-a-concatenated-string-with-unique-characters/
// Author: github.com/lzl124631x
// Time: O(2^N)
// Space: O(N)
class Solution {
public:
    int maxLength(vector<string>& A) {
        vector<int> v;
        for (auto &s : A) {
            int bs = 0, i = 0;
            for (; i < s.size(); ++i) {
                int j = s[i] - 'a';
                if (bs >> j & 1) break;
                bs |= 1 << j;
            }
            if (i == s.size()) v.push_back(bs);
        }
        int ans = 0;
        for (int m = 1; m < 1 << v.size(); ++m) {
            int bs = 0, i = 0;
            for (; i < v.size(); ++i) {
                if ((m >> i & 1) == 0) continue;
                if (bs & v[i]) break;
                bs |= v[i];
            }
            ans = max(ans, __builtin_popcount(bs));
        }
        return ans;
    }
};