318. Maximum Product of Word Lengths

Given a string array words, return the maximum value of length(word[i]) * length(word[j]) where the two words do not share common letters. If no such two words exist, return 0.

• new solution update 2022.05.28

struct Trie {
    Trie* next[2];
    bool eof = false;
    int mul = -1;

    Trie() {
        memset(next, 0, sizeof next);
    }

    void insert(int mask, int len, int pos = 27) {
        if(pos == -1) {
            eof = true;
            mul = max(mul, len);
        } else {
            bool bi = mask & (1<<pos);
            if(!next[bi]) next[bi] = new Trie();
            next[bi]->insert(mask, len, pos - 1);
        }
    }

    int query(int mask, int pos = 27) {
        if(pos == -1) return mul;
        int res = 0;
        bool bi = mask & (1<<pos);
        if(bi) {
            if(next[!bi]) res = next[!bi]->query(mask, pos - 1);
        } else {
            if(next[bi]) res = max(res, next[bi]->query(mask, pos - 1));
            if(next[!bi]) res = max(res, next[!bi]->query(mask, pos - 1));
        }
        return res;
    }
};
class Solution {
public:
    int maxProduct(vector<string>& words) {
        Trie* t = new Trie();
        unordered_map<int, int> mp;
        int res = 0;
        for(auto& w : words) {
            int mask = 0;
            for(auto& ch : w) mask |= (1<<(ch-'a'));
            mp[mask] = max(mp[mask], (int)w.length());
        }
        for(auto& [mask, count] : mp) {
            res = max(res, t->query(mask) * count);
            t->insert(mask, count);
        }
        return res;
    }
};

• Time : O(n*m^2)
• Space : O(m)

class Solution {
public:
    int maxProduct(vector<string>& words) {
        int res = 0;
        unordered_map<int, int> masks;
        for(int i = 0; i < words.size(); i++) {
            int mask = 0;
            for(auto ch : words[i]) {
                mask |= 1<<(ch-'a');
            }
            masks[mask] = max(masks[mask],(int)words[i].length());
        }
        for(auto [mask1, len1]: masks) {
            for(auto [mask2, len2]: masks) {
                if(!(mask1 & mask2))
                    res = max(res, len1 * len2);
            }
        }
        return res;
    }
};