Maximum Product of Word Lengths — Bitmask Intersection

Problem

Find the maximum len(words[i]) * len(words[j]) where words share no common letters.

Approach — Bitmask AND Check

Encode each word as 26-bit mask. Two words share no letters iff their masks' AND = 0.

Time: O(n² + n*L) | Space: O(n)

Solutions

Python

class Solution:
    def maxProduct(self, words: list[str]) -> int:
        masks=[0]*len(words)
        for i,w in enumerate(words):
            for c in w: masks[i]|=(1<<(ord(c)-ord('a')))
        best=0
        for i in range(len(words)):
            for j in range(i+1,len(words)):
                if not(masks[i]&masks[j]):
                    best=max(best,len(words[i])*len(words[j]))
        return best

C++

class Solution {
public:
    int maxProduct(vector<string>& words){
        int n=words.size(); vector<int> m(n,0);
        for(int i=0;i<n;i++) for(char c:words[i]) m[i]|=1<<(c-'a');
        int best=0;
        for(int i=0;i<n;i++) for(int j=i+1;j<n;j++)
            if(!(m[i]&m[j])) best=max(best,(int)(words[i].size()*words[j].size()));
        return best;
    }
};

Complexity

Time: O(n² + n*L) | Space: O(n)