Description

Submission

class Solution {
    int ret;
    int n;
    vector<int> taken;
    vector<int> occured;
    vector<int> uniq;

    void dfs(int cur, vector<string>& arr, int count, vector<vector<int>>& connect) {
        if(cur == n) {
            ret = max(ret, count);
            return;
        }
        bool take = true;
        for(int i = 0; i < cur; ++i) {
            if(taken[i] && !connect[i][cur]) take = false;
        }

        if(uniq[cur] && take) {
            taken[cur] = 1;
            dfs(cur+1, arr, count+arr[cur].size(), connect);    
            taken[cur] = 0;
        }
        
        dfs(cur+1, arr, count, connect);

    }

public:
    int maxLength(vector<string>& arr) {
        ret = 0;
        n = arr.size();
        taken.resize(n, 0);

        // cout << 1;

        vector<int> cnt(26, 0);
        uniq.resize(n, 1);
        for(int i = 0; i < n; ++i) {
            fill(cnt.begin(), cnt.end(), 0);
            for(char ch: arr[i]) {
                if(cnt[ch-'a']) {
                    uniq[i] = 0;
                    break;
                }
                cnt[ch-'a'] = 1;
            }
        }

        vector<vector<int>> connect(n, vector<int>(n, 1));
        for(int i = 0; i < n; ++i) {
            for(int j = i + 1;j < n; ++j) {
                bool finished = false;
                if(finished) break;
                for(auto x: arr[i]) {
                    for(auto y: arr[j]) {
                        if(x == y) {
                            connect[i][j] = 0;
                            finished = 1;
                        }
                    }
                }
            }
        }

        dfs(0, arr, 0, connect);

        return ret;
    }
};

Submission 2

class Solution {
public:
    int maxLength(vector<string>& arr) {
        vector<int> dp {0};
        int ret = 0;

        for(auto& s: arr) {
            int n = 0;
            for(char ch: s) {
                n = n | (1 << (ch-'a'));
            }
            if(__builtin_popcount(n) < s.length()) continue;

            for(int i = dp.size() - 1; i >= 0; --i) {
                if(dp[i]&n) continue;
                dp.push_back(dp[i] | n);
                ret = max(ret, __builtin_popcount(dp.back()));
            }
        }
        return ret;
    }
};