318. Maximum Product of Word Lengths

Medium

---

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.

Example 1:

Input: words = ["abcw","baz","foo","bar","xtfn","abcdef"]
Output: 16
Explanation: The two words can be "abcw", "xtfn".

Example 2:

Input: words = ["a","ab","abc","d","cd","bcd","abcd"]
Output: 4
Explanation: The two words can be "ab", "cd".

Example 3:

Input: words = ["a","aa","aaa","aaaa"]
Output: 0
Explanation: No such pair of words.

Constraints:

• 2 <= words.length <= 1000

• 1 <= words[i].length <= 1000

• words[i] consists only of lowercase English letters.

class Solution:
    def maxProduct(self, words: List[str]) -> int:
        bits = [0]*len(words)
        for index, word in enumerate(words):
            for char in list(word):
                # Here we are simply record occurence of each char in bit place
                # For Example "a" will set 0001 "b" will set 0010, each character will set its own place in 
                # 26 length bit array and when we perform AND operation we will get 0 if no character matches.
                bits[index] |= (1 << (ord(char) - ord('a')))
        product = 0
        for i in range(len(words)):
            for j in range(i, len(words)):
                if (bits[i] & bits[j]) == 0 and len(words[i])*len(words[j]) > product:
                    product = len(words[i])*len(words[j])
        return product