Skip to main content

318. Maximum Product of Word Lengths

medium

Given a list of lowercase words, find the maximum product of two word lengths that share no letters. The bitmask trick encodes each word's letter-set into a single int.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Problem

Given a string array words, return the maximum value of length(word[i]) * length(word[j]) where the two words do not share common letters. If no such two words exist, return 0.

Constraints

  • 2 <= words.length <= 1000
  • 1 <= words[i].length <= 1000
  • words[i] consists only of lowercase English letters.

Examples

Example 1

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

Explanation: The two words can be "abcw", "xtfn".

Example 2

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

Explanation: The two words can be "ab", "cd".

Example 3

Input
words = ["a","aa","aaa","aaaa"]
Output
0

Explanation: No such pair of words.

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

Comparing letter sets naively is O(n^2 * L). With n = 1000 and L = 1000 that's borderline.

Hint 2

26 lowercase letters fit in 26 bits. Encode each word as a single 26-bit int: bit i set iff the word contains 'a' + i.

Hint 3

Two words share no letters iff their bitmasks AND to 0. Now the inner check is O(1).

Solution approach

Reveal approach

Bitmask per-word encoding. Precompute masks[i] and lens[i] for each word: masks[i] has bit (c - 'a') set for each character c in words[i], and lens[i] is the word's length. Then double-loop over pairs (i, j) with i < j: if (masks[i] & masks[j]) == 0 the words share no letters, so update best = max(best, lens[i] * lens[j]). Return best. The mask check replaces a 26-element-or-O(L) set intersection with a single AND. Total time is O(sum_of_lengths) for the precompute plus O(n^2) for the pair scan; with n <= 1000 that's 10^6 — fast. O(n) extra space for the masks and lengths.

Complexity

Time
O(L + n^2)
Space
O(n)

Related patterns

  • bit-manipulation

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Google
  • Amazon

Practice these live with InterviewChamp.AI

Drill Maximum Product of Word Lengths and Bit Manipulation problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →