Nice brute force problem

maxLenghtOfSubsetOfStrings.md

Nice problem from leetcode: https://leetcode.com/problems/maximum-length-of-a-concatenated-string-with-unique-characters/submissions/

Given a set of strings, find a subset of these strings such that:

1. This subset is max{sum length(strings)}
2. All the characters in this subset are unique

We can of course conseder a vectors from {0,1}^26 instead of strings. If we say that there is an edge between two these vectors iff a & b == 0, the problem is to find a clique in the graph such that the & a -> max where a is vertex in this clique. So we need to consider all the cliques and find the maximum.

What makes this solution interesting is the way we iterate. We put valid cliques to the prevMask and try to add a new vertex (represented by m).

class Solution {
public:
    int maxLength(vector<string>& arr) {
        int res = 0;
        vector<int> prevMask = {0}; // encodes all the considered subsets
        for (auto& s : arr) {
            int m = 0;
            for (char c : s)
                m = m | (1<<(c - 'a'));
            if (__builtin_popcount(m) != s.size())
                continue;
            
            // start from end to avoid masks added for the current string
            for (int i = prevMask.size() - 1; i >= 0; --i) {
                if ((prevMask[i] & m) != 0)
                    continue;
                int newSubsetmask = prevMask[i] | m;
   
                prevMask.push_back(newSubsetmask);
                // sinse all the characters are unique
                res = max(res, __builtin_popcount(newSubsetmask));
            }
        }
        
        return res;
    }
};