272. Maximum Product of Word Lengths
You are given an array of strings words, each made of lowercase English letters.
Call two words disjoint if they share no letter at all — no character appears in both. Among all pairs of disjoint words (words[i], words[j]) with i != j, find the one whose product of lengths length(words[i]) × length(words[j]) is largest.
Return that maximum product as an integer. If every pair of words shares at least one letter, return 0.
The intended challenge is making the "do these two words share a letter?" check essentially free.
Example 1:
Input: words = ["abcw", "baz", "foo", "bar", "xtfn", "abcdef"]
Output: 16
Explanation: "abcw" and "xtfn" have no letter in common, giving 4 × 4 = 16. Longer pairs like "abcdef" with anything all collide on some letter.
Example 2:
Input: words = ["a", "ab", "abc", "d", "cd", "bcd", "aeiou"]
Output: 15
Explanation: "bcd" and "aeiou" are disjoint: 3 × 5 = 15. Every larger-length combination shares a letter.
Constraints:
- 2 ≤ words.length ≤ 1000
- 1 ≤ words[i].length ≤ 1000
- words[i] consists of lowercase English letters only.
Hints:
Comparing two words letter by letter costs up to the sum of their lengths, and you do it for every pair. What tiny summary of a word answers "do we overlap?" instantly?
Only which of the 26 letters appear matters, not how often or in what order — that fits in a 26-bit integer. Set bit (c − 'a') for each character c. Two words are disjoint exactly when the bitwise AND of their masks is 0.
Precompute all masks and lengths once, then scan the n² / 2 pairs with a single AND and multiply.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: words = ["abcw", "baz", "foo", "bar", "xtfn", "abcdef"]
Expected output: 16