LeetCode Solutions Blog

Maximum Product of Word Lengths

Number: 318

Difficulty: Medium

Paid? No

Problem Description

Given an array of strings, determine the maximum product of the lengths of two words such that the two words do not share any common letters. If no such pair exists, return 0.

Key Insights

Represent each word as a bitmask where each bit corresponds to a letter in the alphabet.
Precompute these bit masks for all words to quickly check for overlapping letters.
Iterate over all pairs of words and use bitwise AND to determine if they share any letters.
Update the maximum product whenever you find a valid pair.

Space and Time Complexity

Time Complexity: O(n^2 + n * k) where n is the number of words and k is the average length of the words (for creating the bit masks). Space Complexity: O(n) for storing the bit masks and lengths.

Solution

The solution involves first converting each word into an integer bitmask where each bit represents a letter from 'a' to 'z'. This conversion allows for efficient comparison using bitwise operations. For every pair of words, a bitwise AND of their masks indicates whether they share any letters (an AND result of zero means no letters in common). The maximum product of lengths among all such valid pairs is then returned.

Code Solutions

# Function to compute the maximum product of word lengths without common letters
def maxProduct(words):
    n = len(words)
    bitMasks = [0] * n  # List to store bitmask for each word
    lengths = [0] * n   # List to store the length of each word

    # Precompute bitmask for each word
    for i, word in enumerate(words):
        mask = 0
        for char in word:
            # Set the bit corresponding to the letter found in the word
            mask |= 1 << (ord(char) - ord('a'))
        bitMasks[i] = mask
        lengths[i] = len(word)
    
    max_product = 0
    # Compare each pair of words
    for i in range(n):
        for j in range(i + 1, n):
            # Check if words have no common letters using bitwise AND
            if bitMasks[i] & bitMasks[j] == 0:
                product = lengths[i] * lengths[j]
                if product > max_product:
                    max_product = product
    return max_product

# Example usage:
if __name__ == "__main__":
    words = ["abcw", "baz", "foo", "bar", "xtfn", "abcdef"]
    print(maxProduct(words))  # Expected output: 16