Abstract / Summary

Given a list of words, find the maximum product of the lengths of two words that do not share any letters.

Note

The full problem description, including helpful examples, can be found on LeetCode.

This problem is ranked as

and has an acceptance rate of about 61% (400k+ submissions).

Typical patterns to solve this problem:

• Array
• Bit Manipulation
• String

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.

Overview

The provided implementation defines a class Solution with a method maxProduct that receives a list of strings and returns the maximum product of the lengths of two distinct words that share no common characters. The algorithm relies on representing each word as a 26-bit integer mask, grouping words that share the same mask, and then testing mask pairs for disjointness.

Core Steps

Bitmask Construction

A helper function creates a compact integer representation of the characters present in a word.

def bitmask(word):
    mask = 0
    for c in w:
        mask |= 1 << (ord(c) - ord('a'))
    return mask

Each character c contributes a single bit at the position corresponding to its alphabetical index. The resulting mask enables constant-time set-intersection checks using bitwise &.

Grouping by Mask

The method builds a dictionary that maps each unique mask to the set of words that produce it.

longest = defaultdict(set)
for w in words:
    mask = bitmask(w)
    longest[mask].add(w)

Storing words in a set eliminates duplicate entries for the same mask while preserving all candidates that share the exact character composition.

Pairwise Evaluation

The algorithm iterates over every word, recomputes its mask, and then scans the dictionary keys to find masks that are completely disjoint. For each compatible mask, it examines the associated words, skips the current word itself, and updates the best product found.

result = 0
for w in words:
    me   = len(w)
    mask = bitmask(w)
    for l in longest:
        if mask & l == 0:
            for o in longest[l]:
                if o != w:
                    other = len(o)
                    result = max(result, me * other)

The inner if mask & l == 0 test is the decisive filter that discards any pair sharing at least one character, allowing the algorithm to focus only on viable candidates.

Final Result

After all combinations have been examined, the method returns the highest product recorded.

return result

Edge Cases Handled

When the input list is empty or contains a single element, the outer loop runs but never finds a distinct partner, leaving result at its initial value of 0. This correctly reflects the fact that no valid pair exists.

If multiple words are identical or consist of the same set of letters, they map to the same mask and reside in the same set within longest. The inner check if o != w ensures that a word is never paired with itself, even when duplicates are present.

Words that contain every letter of the alphabet generate a mask with all 26 bits set. Such a mask will never satisfy the disjointness condition with any other mask, so the algorithm naturally excludes these cases without extra logic.

When a word is an empty string, its mask remains 0. The disjointness test mask & l == 0 will succeed for any other mask, allowing the empty word to be paired with any other word. The product will be zero because the length of the empty string is zero, which the algorithm correctly records as a possible (though not maximal) result.

Performance Optimizations

The primary optimization is the conversion of each word into a 26-bit integer. This representation compresses the character set into a single machine word, enabling the algorithm to test for shared characters with a single bitwise & operation, which is far faster than iterating over characters or using set intersections.

Grouping words by their mask reduces redundant work. Instead of comparing every word against every other word directly, the code compares each mask against the distinct set of masks stored as dictionary keys. This eliminates repeated mask calculations for words that share the same character composition.

Storing words in a set under each mask prevents duplicate entries from inflating the inner loop, ensuring that each distinct word is considered at most once per compatible mask.

The use of max to update the result avoids conditional branching beyond the necessary comparison, keeping the inner loop tight and cache-friendly.

Overall, the combination of bitwise masking, dictionary grouping, and set storage yields an approach that scales efficiently with the number of input words while keeping the inner operations lightweight.

Imagine the alphabet is a line of buckets labeled from a to z. Every time a new word is picked up, it is checked for letters. If a word has the letter a, a little marble is dropped into the first bucket. If it has a b, a marble goes into the second bucket. By the end, each word turns into a secret string of numbers that shows which letters it uses.

When looking for two words that do not share any letters, the secret strings are compared. If the result of comparing them is zero, it means they have no buckets in common. This ensures that the words are totally different, like a cat and a dog. Once two words are found that do not overlap, their lengths are multiplied together to see how big the area would be if they were sides of a rectangle. The goal is to keep track of the biggest rectangle found during this search.

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):

Time: polynomial
As a rule of thumb, the maximum input size for one second execution time is

• factorial: up to 10 elements
• exponential: up to 20 elements
• polynomial: a few thousand elements
• loglinear: up to 100,000 elements
• linear: a few million elements
• logarithmic: a billion elements
• constant: practically unlimited

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)

	author
author	solutions
www	AlgoMonster	C++	Java	Python							TS
	WalkCCC	C++	Java	Python
	leetcode.ca	C++	Java	Python					Go		TS
	LeetcodeHelp	C++	Java	Python
	MemoryLimitExceeded	C++		Python
	Progiez	C++	Java	Python
github	black-shadows	C++
	charles-wangkai		Java
	chenyanzhe	C++
	everthis				JS
	fartem							Ruby
	FelixFan1122					C#
	fengvyi	C++
	fpdjsns	C++
	halfrost								Go
	haoel	C++
	JoshCrozier				JS
	keineahnung2345	C++
	linouk23	C++
	lkwq007			Python
	ruoru						Rust
	suxrobGM					C#
	varunu28		Java
	vli02									C
	vthwang		Java
	wisdompeak	C++
	XiaotaoGuo	C++
	YuriSpiridonov			Python
	zfang399	C++
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, Go, Java, Python, TypeScript
LeetcodeHelp	C++, Java, Python
MemoryLimitExceeded	Python, C++
Progiez	C++, Java, Python
black-shadows	C++, C++
charles-wangkai	Java
chenyanzhe	C++
everthis	JavaScript
fartem	Ruby
FelixFan1122	C#
fengvyi	C++
fpdjsns	C++
halfrost	Go
haoel	C++
JoshCrozier	JavaScript
keineahnung2345	C++
linouk23	C++
lkwq007	Python
ruoru	Rust
suxrobGM	C#
varunu28	Java
vli02	C
vthwang	Java
wisdompeak	C++
XiaotaoGuo	C++
YuriSpiridonov	Python
zfang399	C++

There are a few extra pages giving you some insights into my setup:

• Tech Stack - my development environment and tools
• AI - how AI helped me create this website (NOT solving the problems)
• Progress - progression over time
• Quality - code quality