NUHMAN.com

Introduction

LeetCode 318: Maximum Product of Word Lengths asks us to find two words from a list of words such that the product of their lengths is maximized, and the two words do not share any common letters. This problem can be solved efficiently using bit manipulation, leveraging a bitmask representation of each word to determine if two words share common letters.

By converting each word into a bitmask, we can quickly determine whether two words have common letters using a simple bitwise AND operation. This allows us to optimize the solution and achieve better performance than a brute-force approach.

Problem Statement

Given a list of words, you need to find the maximum product of the lengths of two words such that the two words do not have any common letters.

Input:

• words = ["abcw", "baz", "foo", "bar", "xtfn", "abcdef"]

Output:

• 16 (because the words "abcw" and "xtfn" have no common letters and the product of their lengths is 4 * 4 = 16)

Example

python

# Example 1
Input: words = ["abcw", "baz", "foo", "bar", "xtfn", "abcdef"]
Output: 16

# Example 2
Input: words = ["a", "ab", "abc", "d", "cd", "bcd", "abcd"]
Output: 4

Step-by-Step Solution

🧠 Intuition

We need to find pairs of words that don’t share any common letters, and then calculate the product of their lengths. A brute-force solution would involve comparing each pair of words and checking whether they share common letters, which would take O(n²) time. However, we can optimize this by using bitmasking.

✅ Approach

1. Bitmask Representation:
2. Each word can be represented as a 32-bit integer, where each bit corresponds to a letter of the alphabet. For example:

• Word "abc" can be represented as a bitmask where the first three bits are 1 (indicating the presence of letters a, b, and c).

1. This allows us to encode the information about which letters a word contains using bitwise operations. This is very efficient because checking whether two words share any common letter can then be done in constant time using a bitwise AND operation.
2. Checking Common Letters:
3. To check if two words share common letters, we perform a bitwise AND on their bitmask representations. If the result is 0, the words do not share any common letters.
4. Calculate Maximum Product:
5. For each pair of words, if they do not share common letters (i.e., the bitwise AND of their bitmasks is 0), we compute the product of their lengths and keep track of the maximum product.
6. Optimization:
7. Instead of checking all pairs of words in a brute-force manner, we compute the bitmask for each word and store it along with its length. This allows us to quickly compare any two words using their bitmask representations.

✅ Python Code

python

class Solution:
    def maxProduct(self, words: list[str]) -> int:
        # Function to convert a word to a bitmask representation
        def word_to_bitmask(word: str) -> int:
            bitmask = 0
            for char in word:
                bitmask |= (1 << (ord(char) - ord('a')))
            return bitmask
        
        n = len(words)
        bitmasks = [word_to_bitmask(word) for word in words]
        max_product = 0
        
        # Compare each pair of words
        for i in range(n):
            for j in range(i + 1, n):
                if bitmasks[i] & bitmasks[j] == 0:  # No common letters
                    max_product = max(max_product, len(words[i]) * len(words[j]))
        
        return max_product

Explanation of the Code

1. word_to_bitmask Function:
2. This helper function converts a word into a bitmask. For each character in the word, we use the bitwise OR (|) operator to set the corresponding bit in the bitmask. For example, the letter 'a' corresponds to the first bit, 'b' corresponds to the second bit, and so on.
3. Bitmask Computation:
4. We compute the bitmask for each word and store these bitmasks in the bitmasks list.
5. Max Product Calculation:
6. We loop through all pairs of words (indexed by i and j) and check if their bitmasks have no common bits set (i.e., bitmasks[i] & bitmasks[j] == 0). If they don’t share any letters, we compute the product of their lengths and update max_product if this product is greater than the current maximum.

⏱️ Time and Space Complexity

MetricValueTime ComplexityO(n²)Space ComplexityO(n)

• Time Complexity:
• We loop through each pair of words, so the time complexity is O(n²), where n is the number of words in the list. For each pair, we check whether their bitmasks share common letters, which is a constant-time operation. Therefore, the overall time complexity is O(n²).
• Space Complexity:
• We store the bitmask for each word, which takes O(n) space where n is the number of words.

🔍 Edge Cases

1. Empty List of Words:
2. If the input list of words is empty, the result should be 0 since there are no words to compare.
3. Single Word in List:
4. If the list contains only one word, the result should be 0 because there is no other word to form a product with.
5. Words with Common Letters:
6. If all words share common letters, the result should be 0 because no two words can form a valid pair without common letters.
7. All Words with Unique Letters:
8. If every word contains only unique letters, the solution should correctly calculate the maximum product for the words that do not share any letters.

✅ Conclusion

LeetCode 318: Maximum Product of Word Lengths is an optimization problem where bit manipulation (bitmasking) helps us efficiently determine the maximum product of lengths for pairs of words that do not share any common letters. By using bitwise operations, we can reduce the time complexity significantly compared to a brute-force approach, making this problem solvable even with large input sizes.