318 Maximum Product of Word Lengths

Given a string arraywords, find the maximum value oflength(word[i]) * length(word[j])where the two words do not share common letters. You may assume that each word will contain only lower case letters. If no such two words exist, return 0.

Example 1:

Given["abcw", "baz", "foo", "bar", "xtfn", "abcdef"] Return16 The two words can be"abcw", "xtfn".

Example 2:

Given["a", "ab", "abc", "d", "cd", "bcd", "abcd"] Return4 The two words can be"ab", "cd".

Example 3:

Given["a", "aa", "aaa", "aaaa"] Return0 No such pair of words.

Brute Force:

The Idea: For each combination of words whose intersection return the empty set, return the maximum product of their lengths.

Complexity: O(n^2 * m) where N is the number of words, and M is the length of a word.

class Solution:
    def maxProduct(self, words):
        """
        :type words: List[str]
        :rtype: int
        """
        max_prod = 0
        for i in range(0, len(words)):
            for j in range(i + 1, len(words)):
                if set(words[i]) & set(words[j]) == set():
                    max_prod = max(len(words[i]) * len(words[j]), max_prod)
        return max_prod

Optimal:

The Idea: Create a unique binary representation of the each word. We can do so by setting each bit for each character in the word. Then we can do the same thing as before and check if the intersection of each word (in this case there binary fingerprint), and look for the empty set, or 0.

Complexity: O(2N*M) time and O(N) space

import string


class Solution:
    def maxProduct(self, words):
        """
        :type words: List[str]
        :rtype: int
        """
        char_int = {char: i for i, char in enumerate(list(string.ascii_lowercase))}
        word_map = [0] * len(words)

        for i, word in enumerate(words):
            for char in word:
                word_map[i] |= 1 << char_int[char]

        max_product = 0
        for i in range(0, len(words)):
            for j in range(i+1, len(words)):
                if not word_map[i] & word_map[j]: # O(1) processing time
                    max_product = max(max_product, len(words[i]) * len(words[j]))

        return max_product