Maximum Product of Word Length

Problem: Maximum Product of Word Length

We can use a 26-bit-long mask to identify each word. 1 or 0 on each bit represents whether there's certain character in the word. Thus, masks of words with totally different letters will surely AND up to 0.

Code in Python:

from collections import defaultdict

class Solution(object):
    def maxProduct(self, words):
        """
        :type words: List[str]
        :rtype: int
        """
        mask_len = defaultdict(int)

        for word in words:
            mask = 0
            for c in word:
                mask |= 1 << (ord(c)-ord('a'))
            mask_len[mask] = max(mask_len[mask], len(word))

        res = 0
        n = len(mask_len)
        _mask_len = mask_len.items()
        for i in xrange(n):
            for j in xrange(i):
                if not _mask_len[i][0] & _mask_len[j][0]: res = max(res, _mask_len[i][1]*_mask_len[j][1])
        return res