Maximum Product of Word Lengths

Given a list of words, return the maximum value of length(word[i]) * length(word[j]) such that the two words do not share any common letters. Pattern focus: Bitmask Enumeration. Convert each word into a bitmask of used letters and compare masks efficiently.

Input Format

words = list of lowercase words

Output Format

maximum product of lengths of two words with no common letters

Constraints

  • 1 <= input size <= 10^5
  • -10^9 <= numeric values <= 10^9
  • words must satisfy the format described in inputFormat.

Examples

Example 1:

Input:

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

Output:

16

Explanation:

The pair abcw and xtfn shares no letters and gives 4 * 4 = 16.

Example 2:

Input:

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

Output:

4

Explanation:

The pair a and bcd gives the best product.

Loading...
Maximum Product of Word Lengths