Problem 34.9 · Bit ManipulationMedium

Maximum Product of Word Lengths

What it teaches: A 26-bit mask per word turns "no common letters" into one AND.

Practise it on judges as “Maximum Product of Word Lengths”.

The problem

Return the maximum length(a) × length(b) over pairs of words with no letters in common, or 0.

Example 1

Input: words = [abcw, baz, foo, bar, xtfn, abcdef]
Output: 16

abcw × xtfn.

Constraints

2 ≤ words ≤ 1000
Lowercase letters

Pattern clues in the wording

→ Compare letter sets of many pairs

These clues point to Bit Manipulation: Use XOR, AND, OR and shifts to test, set and cancel bits, often in O(1) space.

Stuck? Take one hint at a time

Solution.java · starter

class Solution {
    public int maxProduct(String[] words) {
        return 0;
    }
}

Write your solution locally or in your editor for now. The in-browser runner (Java first, then Python, C++ and more) will run these tests right here.

Test cases

#	Input	Expected
1	words = ["abcw","baz","foo","bar","xtfn","abcdef"]	16
2	words = ["a","ab","abc","d","cd","bcd","abcd"]	4
3	words = ["a","aa","aaa","aaaa"]	0

From slow to fast

Approaches

1. Letter masks · O(total letters + n²)

Letter masks

Time O(total letters + n²) Space O(n)

Precompute masks; check all pairs with one AND each.

Approach 1

class Solution {
    public int maxProduct(String[] words) {
        int n = words.length, best = 0;
        int[] mask = new int[n];
        for (int i = 0; i < n; i++)
            for (char c : words[i].toCharArray()) mask[i] |= 1 << (c - 'a');
        for (int i = 0; i < n; i++)
            for (int j = i + 1; j < n; j++)
                if ((mask[i] & mask[j]) == 0) best = Math.max(best, words[i].length() * words[j].length());
        return best;
    }
}

Verdict: Each pair check is O(1).

Before you submit

Edge cases and common mistakes

Test these inputs

All words share a letter (0)
Duplicate words

Mistakes people make

Comparing letter sets with nested loops over characters (O(n² × L²)).

Interview

Follow-up questions

How can duplicate masks be reduced?

Command Palette

The problem

Approaches

Letter masks

Edge cases and common mistakes

Follow-up questions