LeetCode 318: Maximum Product of Word Lengths Solution in Python – A Step-by-Step Guide

What Is LeetCode 318: Maximum Product of Word Lengths?

In LeetCode 318: Maximum Product of Word Lengths, you’re given an array of strings words, and your task is to find the maximum value of len(word[i]) * len(word[j]) where word[i] and word[j] share no common letters (i ≠ j). For example, with ["abcw", "baz", "foo", "bar", "xtfn", "abcdef"], the max product is 16 ("abcw" and "xtfn"). This problem tests your ability to check for common characters efficiently and optimize pairwise comparisons.

Problem Statement

• Input: An array of strings words.
• Output: An integer—the maximum product of two word lengths with no common letters, or 0 if impossible.
• Rules:
• Words must have no overlapping letters.
• Choose distinct words (i ≠ j).
• Return 0 if no valid pair exists.

Constraints

• 2 <= words.length <= 1000
• 1 <= words[i].length <= 1000
• words[i] contains only lowercase English letters.

Examples

• Input: ["abcw","baz","foo","bar","xtfn","abcdef"]
• Output: 16 ("abcw" * "xtfn" = 4 * 4)
• Input: ["a","ab","abc","d","cd","bcd","abcd"]
• Output: 4 ("ab" * "cd" = 2 * 2)
• Input: ["a","aa","aaa","aaaa"]
• Output: 0 (No pair without common letters)

Understanding the Problem: Maximizing Length Products

To solve LeetCode 318: Maximum Product of Word Lengths in Python, we need to find two words with no common letters and maximize their length product. A naive approach—checking every pair with character comparisons—is O(n² * L), where n is the number of words and L is the max word length—too slow for large inputs. Instead, we’ll use:

• Best Solution (Bitmask): O(n² + n*L) time, O(n) space—fast and efficient.
• Alternative Solution (Sets): O(n² * L) time, O(n*L) space—intuitive but slower.

Let’s start with the bitmask solution, explained in a beginner-friendly way.

Best Solution: Bitmask Approach

Why This Is the Best Solution

The bitmask approach is the top choice for LeetCode 318 because it’s efficient—O(n² + n*L) time, O(n) space—and cleverly uses bit manipulation to check for common letters in O(1) time per pair. It precomputes a bitmask for each word, where each bit represents a letter’s presence, then compares pairs using bitwise AND. It’s like giving each word a unique fingerprint—quick and smart!

How It Works

Think of this as a binary word game:

• Step 1: Create Bitmasks:
• For each word, set a bit for each letter (a=0th bit, b=1st, etc.).
• E.g., "ab" = 1<<0 | 1<<1 = 3.
• Step 2: Compare Pairs:
• If mask[i] & mask[j] == 0, no common letters.
• Compute length product for valid pairs.
• Step 3: Track Maximum:
• Update max product as you go.
• Step 4: Why It Works:
• Bitwise AND checks overlap in O(1).
• Preprocessing reduces per-pair cost.

It’s like matching word fingerprints—super fast!

Step-by-Step Example

Example: words = ["abcw","baz","foo","xtfn"]

• Bitmasks:
• "abcw": a(1), b(2), c(4), w(1<<22) = 4194311
• "baz": b(2), a(1), z(1<<25) = 33554435
• "foo": f(1<<5), o(1<<14) = 16416
• "xtfn": x(1<<23), t(1<<19), f(32), n(1<<13) = 9437440
• Pairs:
• "abcw" & "baz": 4194311 & 33554435 = 3 ≠ 0
• "abcw" & "xtfn": 4194311 & 9437440 = 0, Product = 4*4 = 16
• "baz" & "xtfn": 33554435 & 9437440 = 0, Product = 3*4 = 12
• "foo" & "xtfn": 16416 & 9437440 = 0, Product = 3*4 = 12
• Result: Max = 16

Code with Detailed Line-by-Line Explanation

Copy codeclass Solution:
    def maxProduct(self, words: List[str]) -> int:
        n = len(words)
        # Precompute bitmasks and lengths
        masks = [0] * n
        lengths = [0] * n
        for i, word in enumerate(words):
            for char in word:
                masks[i] |= 1 << (ord(char) - ord('a'))  # Set bit for char
            lengths[i] = len(word)

        # Find max product
        max_prod = 0
        for i in range(n):
            for j in range(i + 1, n):
                if masks[i] & masks[j] == 0:  # No common letters
                    max_prod = max(max_prod, lengths[i] * lengths[j])

        return max_prod

• Line 3: Get number of words.
• Lines 5-9: Build bitmasks and lengths:
• Shift 1 by char position, OR to combine.
• Lines 12-16: Compare pairs:
• Bitwise AND checks overlap.
• Update max product if no common letters.
• Time Complexity: O(n² + n*L)—preprocessing O(n*L), pairs O(n²).
• Space Complexity: O(n)—masks and lengths arrays.

This is like a bit-powered word matcher—swift and slick!

Alternative Solution: Set-Based Approach

Why an Alternative Approach?

The set-based approach also works—O(n² * L) time, O(n*L) space—using sets to check for common letters explicitly. It’s more intuitive for those new to bit manipulation, though slower due to set operations. It’s like comparing word letter bags—clear and straightforward!

How It Works

Check pairs with sets:

• Step 1: Convert each word to a set of letters.
• Step 2: Compare all pairs:
• If intersection is empty, compute product.
• Step 3: Track maximum.

Step-by-Step Example

Example: words = ["abc","de"]

• Sets: {"a","b","c"}, {"d","e"}
• Pairs:
• {"a","b","c"} ∩ {"d","e"} = ∅, Product = 3*2 = 6
• Result: 6

Code for Set-Based Approach

Copy codeclass Solution:
    def maxProduct(self, words: List[str]) -> int:
        n = len(words)
        # Precompute sets
        char_sets = [set(word) for word in words]

        # Find max product
        max_prod = 0
        for i in range(n):
            for j in range(i + 1, n):
                if not (char_sets[i] & char_sets[j]):  # No common letters
                    max_prod = max(max_prod, len(words[i]) * len(words[j]))

        return max_prod

• Time Complexity: O(n² * L)—set intersection O(L) per pair.
• Space Complexity: O(n*L)—sets storage.

It’s a set-driven word checker—simple but slower!

Comparing the Two Solutions

• Bitmask (Best):
• Pros: O(n² + n*L) time, O(n) space, fast checks.
• Cons: Bit manipulation less intuitive.
• Set-Based (Alternative):
• Pros: O(n² * L) time, O(n*L) space, easy to understand.
• Cons: Slower, more memory.

Bitmask wins for performance.

Additional Examples and Edge Cases

• ["a","b"]: 1.
• ["aa","aa"]: 0.
• ["abc"]: 0 (No pair).

Both handle these well.

Complexity Breakdown

• Bitmask: Time O(n² + n*L), Space O(n).
• Set-Based: Time O(n² * L), Space O(n*L).

Bitmask is faster and leaner.

Key Takeaways

• Bitmask: Bits beat sets—efficient!
• Set-Based: Clarity over speed—educational!
• Python: Bit ops and sets shine—see [Python Basics](/python/basics).
• Words: Disjoint pairs are key.

Final Thoughts: Multiply Those Lengths

LeetCode 318: Maximum Product of Word Lengths in Python is a fun optimization challenge. The bitmask solution offers speed and elegance, while the set-based method provides a clear baseline. Want more string puzzles? Try LeetCode 316: Remove Duplicate Letters or LeetCode 438: Find All Anagrams in a String. Ready to multiply? Head to Solve LeetCode 318 on LeetCode and max out that product today!