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 Sam K., 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

More Bit Manipulation practice problems

See all Bit Manipulation problems →