1239. Maximum Length of a Concatenated String with Unique Characters

You are given an array of strings arr. A string s is formed by the concatenation of a subsequence of arr that has unique characters.

Return the maximum possible length of s.

A subsequence is an array that can be derived from another array by deleting some or no elements without changing the order of the remaining elements.

class Solution {
public:
    int maxLength(vector<string>& arr) {
        int n = arr.size(), res = 0;
        vector<int> bits;
        for(int i = 0; i < n; i++) {
            int bi = 0;
            bool unique = true;
            for(auto& ch : arr[i]) {
                if(bi & (1<<(ch-'a'))) unique = false;
                bi |= 1<<(ch-'a');
            }
            if(unique)
                bits.push_back(bi);
        }
        n = bits.size();
        for(int subset = 0; subset < 1<<n; subset++) {
            int mask = 0;
            bool unique = true;
            for(int i = 0; i < n and unique; i++) {
                if(!(subset & (1<<i))) continue;
                if(mask & bits[i]) {
                    unique = false;
                } else mask ^= bits[i];
            }
            if(unique)
                res = max(res, __builtin_popcount(mask));
        }
        return res;
    }
};