LeetCode Problem 318

Difficulty: 🟡 Medium
Topics: Array, String, Bit Manipulation

Solution

LeetCode 318 - Maximum Product of Word Lengths

Problem Understanding

The problem gives us an array of lowercase English words. We need to find two different words such that they do not share any common letters, then return the maximum possible product of their lengths.

More formally, for every pair of indices (i, j) where i != j, we check whether words[i] and words[j] contain any overlapping characters. If they do not share any letters, we compute:

$$\text{len(words[i])} \times \text{len(words[j])}$$

Among all valid pairs, we return the largest product.

For example, if the words are:

["abcw","baz","foo","bar","xtfn","abcdef"]

The pair "abcw" and "xtfn" shares no common characters. Their lengths are 4 and 4, so the product is:

4 * 4 = 16

This is the maximum possible answer.

The constraints are important:

• There can be up to 1000 words.
• Each word can have length up to 1000.
• Words contain only lowercase English letters.

A naive approach that compares every character of every pair could become expensive because there are up to:

$$1000 \times 1000 = 10^6$$

word pairs, and each comparison could involve scanning many characters.

The key observation is that there are only 26 lowercase English letters. This makes bit manipulation extremely effective.

Several edge cases are important:

• All words may share at least one common character, producing answer 0.
• Very short words such as single characters can still form the maximum product.
• Duplicate letters inside the same word should not matter. For example, "aaaa" still only contains the letter 'a'.
• Large words with repeated characters should still be processed efficiently.

Approaches

Brute Force Approach

The most direct solution is to examine every pair of words and determine whether they share a common character.

For each pair:

1. Convert one or both words into sets of characters.
2. Check whether the sets intersect.
3. If they do not intersect, compute the product of lengths.
4. Track the maximum product found.

This approach is correct because it explicitly checks every possible pair and verifies whether the pair satisfies the condition.

However, it is inefficient. There are O(n^2) pairs of words, and checking character overlap can cost up to O(L) where L is the word length. With long words and many pairs, this becomes slow.

Optimal Approach Using Bit Manipulation

The important insight is that each word only contains lowercase English letters, meaning there are only 26 possible characters.

We can represent the set of characters in a word using a 26-bit integer mask.

For example:

• Bit 0 represents 'a'
• Bit 1 represents 'b'
• Bit 2 represents 'c'
• and so on

If a word contains a letter, we set the corresponding bit to 1.

Example:

"abc"

becomes:

111

in binary for the first three bits.

Now consider two words:

• If they share no common letters, their masks will have no overlapping 1 bits.
• We can check this using bitwise AND:

mask1 & mask2 == 0

This makes overlap checking extremely fast, reducing the character comparison cost dramatically.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n² × L)	O(L)	Compares every pair and checks character overlap directly
Optimal	O(n × L + n²)	O(n)	Uses bitmasks for constant-time overlap checks

Here:

• n is the number of words
• L is the average word length

Algorithm Walkthrough

Step 1: Create a Bitmask for Each Word

For every word, build an integer mask representing which letters appear in the word.

Start with:

mask = 0

For each character:

bit = ord(char) - ord('a')
mask |= (1 << bit)

This sets the appropriate bit.

For example:

"abc"

produces:

000...0111

Step 2: Store Word Lengths

Along with each mask, store the word's length.

This prevents repeated calls to len() during pair comparisons.

Step 3: Compare Every Pair of Words

Use two nested loops:

for i in range(n):
    for j in range(i + 1, n):

This checks every unique pair exactly once.

Step 4: Check for Shared Characters

For a pair of masks:

if masks[i] & masks[j] == 0:

then the words share no letters.

Why does this work?

• Shared letters produce overlapping 1 bits.
• Bitwise AND preserves only overlapping bits.
• Result 0 means no overlap exists.

Step 5: Compute Product

If the pair is valid:

product = lengths[i] * lengths[j]

Update the maximum answer if necessary.

Step 6: Return the Maximum Product

After checking all pairs, return the stored maximum.

Why it works

Each word mask exactly represents the set of letters present in that word. Two words share no common characters if and only if their masks have no overlapping bits. The algorithm checks every possible pair of words, so no valid candidate is missed. Because the maximum product is updated whenever a better valid pair is found, the final answer is guaranteed to be correct.

Python Solution

from typing import List

class Solution:
    def maxProduct(self, words: List[str]) -> int:
        n = len(words)

        masks = [0] * n
        lengths = [0] * n

        # Build bitmask for each word
        for i, word in enumerate(words):
            mask = 0

            for char in word:
                bit = ord(char) - ord('a')
                mask |= (1 << bit)

            masks[i] = mask
            lengths[i] = len(word)

        max_product = 0

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

        return max_product

The implementation begins by allocating two arrays:

• masks, which stores the bit representation of each word
• lengths, which stores the length of each word

For every word, we iterate through its characters and set the corresponding bit in the mask. The expression:

mask |= (1 << bit)

ensures that the character's position becomes 1.

After preprocessing, we compare all word pairs using nested loops.

The critical optimization is:

masks[i] & masks[j] == 0

This performs the overlap check in constant time instead of scanning characters repeatedly.

Whenever a valid pair is found, we compute the product of lengths and update max_product.

Finally, we return the largest product discovered.

Go Solution

func maxProduct(words []string) int {
	n := len(words)

	masks := make([]int, n)
	lengths := make([]int, n)

	// Build bitmask for each word
	for i, word := range words {
		mask := 0

		for _, ch := range word {
			bit := ch - 'a'
			mask |= (1 << bit)
		}

		masks[i] = mask
		lengths[i] = len(word)
	}

	maxProduct := 0

	// Compare every pair
	for i := 0; i < n; i++ {
		for j := i + 1; j < n; j++ {
			// No common letters
			if masks[i]&masks[j] == 0 {
				product := lengths[i] * lengths[j]

				if product > maxProduct {
					maxProduct = product
				}
			}
		}
	}

	return maxProduct
}

The Go implementation follows the same logic as the Python version.

One difference is that Go iterates over strings using:

for _, ch := range word

which returns Unicode runes. Since the input only contains lowercase English letters, this is completely safe.

Go also does not provide a built-in max() function for integers, so the code uses a standard conditional comparison when updating maxProduct.

The integer type in Go is large enough for this problem because the maximum product is:

1000 * 1000 = 1,000,000

which easily fits within a 32-bit integer.

Worked Examples

Example 1

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

Step 1: Build Masks

Word	Length	Characters	Bitmask Meaning
abcw	4	a,b,c,w	bits for a,b,c,w
baz	3	b,a,z	bits for a,b,z
foo	3	f,o	bits for f,o
bar	3	b,a,r	bits for a,b,r
xtfn	4	x,t,f,n	bits for x,t,f,n
abcdef	6	a,b,c,d,e,f	bits for a,b,c,d,e,f

Step 2: Compare Pairs

Pair	Shared Letters?	Product
abcw, baz	yes	invalid
abcw, foo	no	12
abcw, bar	yes	invalid
abcw, xtfn	no	16
abcw, abcdef	yes	invalid
foo, xtfn	yes, f	invalid

The maximum valid product is:

4 * 4 = 16

Answer:

16

Example 2

words = ["a","ab","abc","d","cd","bcd","abcd"]

Masks

Word	Mask Contents
a	a
ab	a,b
abc	a,b,c
d	d
cd	c,d
bcd	b,c,d
abcd	a,b,c,d

Valid Pairs

Pair	Product
a, d	1
ab, cd	4
abc, d	3

Maximum:

4

Example 3

words = ["a","aa","aaa","aaaa"]

Every word contains only 'a'.

Thus every pair shares a common character.

No valid pair exists.

Answer:

0

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n × L + n²)	Building masks takes O(n × L), pair comparisons take O(n²)
Space	O(n)	Stores masks and lengths for each word

The preprocessing phase scans every character of every word once, giving O(n × L) complexity.

After preprocessing, each pair comparison becomes constant time because bitwise AND is extremely efficient. Since there are O(n²) pairs, the total comparison cost is O(n²).

The space complexity is O(n) because we store one mask and one length for each word.

Test Cases

solution = Solution()

# Provided examples
assert solution.maxProduct(["abcw","baz","foo","bar","xtfn","abcdef"]) == 16  # standard example
assert solution.maxProduct(["a","ab","abc","d","cd","bcd","abcd"]) == 4  # mixed overlaps
assert solution.maxProduct(["a","aa","aaa","aaaa"]) == 0  # no valid pair

# Minimal valid input
assert solution.maxProduct(["ab", "cd"]) == 4  # two disjoint words

# Single character overlap
assert solution.maxProduct(["ab", "bc"]) == 0  # shared character b

# Duplicate letters inside words
assert solution.maxProduct(["aaaa", "bbbb"]) == 16  # repeated chars should not matter

# Multiple optimal candidates
assert solution.maxProduct(["abc", "def", "ghi"]) == 9  # several valid maximum pairs

# One very large word
assert solution.maxProduct(["abcdefghijklmnopqrstuvwxyz", "a", "bc"]) == 2  # only bc works

# Empty result despite many words
assert solution.maxProduct(["ab", "ba", "aa", "bb"]) == 0  # every pair overlaps

# Long disjoint words
assert solution.maxProduct(["abcdefgh", "ijklmnop"]) == 64  # large valid product

# Mixed valid and invalid pairs
assert solution.maxProduct(["abc", "xy", "xz"]) == 6  # abc and xy

Test Summary

Test	Why
["abcw","baz","foo","bar","xtfn","abcdef"]	Validates standard example
["a","ab","abc","d","cd","bcd","abcd"]	Tests mixed overlaps
["a","aa","aaa","aaaa"]	Ensures zero is returned correctly
["ab","cd"]	Smallest meaningful valid case
["ab","bc"]	Tests overlap detection
["aaaa","bbbb"]	Verifies repeated characters do not affect masks
["abc","def","ghi"]	Multiple maximum candidates
["abcdefghijklmnopqrstuvwxyz","a","bc"]	Tests very large mask
["ab","ba","aa","bb"]	Confirms all-overlap scenario
["abcdefgh","ijklmnop"]	Large valid product
["abc","xy","xz"]	Mixed valid and invalid comparisons

Edge Cases

All Words Share a Common Character

A common mistake is assuming at least one valid pair exists. Consider:

["a", "aa", "aaa"]

Every word contains 'a', so every pair overlaps. The implementation correctly handles this because max_product starts at 0 and is only updated when a valid pair is found.

Words with Repeated Characters

Words may contain repeated letters:

["aaaa", "bbbb"]

A naive implementation might unnecessarily process duplicates repeatedly. The bitmask approach naturally avoids this issue because setting the same bit multiple times has no effect.

For example:

mask |= (1 << bit)

simply keeps the bit set to 1.

Very Large Words

Words can have length up to 1000. Repeatedly comparing characters between pairs could become expensive.

The optimized solution avoids this problem by preprocessing each word once into a compact integer representation. After preprocessing, overlap checking becomes a constant-time bitwise operation regardless of word length.