Bit Manipulation — Maximum Product of Word Lengths
↗ LeetCode: Maximum Product of Word Lengths · Medium · pattern chapter →
Asked atGoogleAmazonMeta
Return max(len(a) * len(b)) over pairs whose character sets are disjoint (no shared letter).
Example 1 — words=["abcw","baz","foo","bar","xtfn","abcdef"] → 16 ("abcw" × "xtfn") Example 2 — words=["a","aa","aaa","aaaa"] → 0
Constraints — 2 ≤ n ≤ 1000; lowercase. Brute compares every pair of words char-by-char — O(n²·L²) = 10⁹ ops at n=10³, L=10³ (TLE). Bitmask of 26-letter presence + AND==0 test is O(n²) = 10⁶ ops.
Progressive Hints
Try to solve it yourself first. Reveal hints only when stuck — each hint is progressively more specific.
Interview timer00:00
Practice under interview pressure. Start when you begin reading; stop when you finish. Save best only when you had a full working solution.
Target for interview: Medium = 20-25 min · Hard = 30-40 min · Best time persists on this device only.
Approach 1 — Set intersection per pair
For each pair build a Set<Character>; check intersection. O(n² · L).
Approach 2 — Bitmask signatures (canonical)
Insight. Each word uses ≤ 26 letters → 26-bit signature. Two words share no letters iff mask[i] & mask[j] == 0. Pair comparison becomes a single AND.
java
int maxProduct(String[] words) {
int n = words.length;
int[] mask = new int[n];
for (int i = 0; i < n; i++)
for (char c : words[i].toCharArray()) mask[i] |= 1 << (c - 'a');
int best = 0;
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;
}Execution Trace
Step 1 / 3Initialize scan.
Complexity — Time O(n·L + n²); Space O(n).
Try it yourself
Complexity summary
| Approach | Time | Space | Grade |
|---|---|---|---|
| Per-pair set intersect | O(n²·L) | O(σ) | baseline |
| Bitmask + AND | O(n·L + n²) | O(n) | canonical |
When to use which
- Small fixed alphabet (≤ 64) → bitmask signatures.
- Larger alphabet → hashed signatures + fingerprint check.
- "Return the pair" → track indices.
AI Study CompanionBeta
Related problems
- Design Bit Set
- Number of Ways to Wear Different Hats — bitmask DP
Was this page helpful?
📚 Related problems