/318. Maximum Product of Word Lengths

318. Maximum Product of Word Lengths

Medium
Arrays61.1% acceptance

Given a list of strings string_list, return the maximum value of len(string_list[i]) * len(string_list[j]) for any two distinct strings string_list[i] and string_list[j] that do not share any common characters. If no such pair exists, return 0.

Example 1

Input: [abcd,efgh,ijkl]

Output: 16

Explanation: abcd and efgh do not share any letters, product is 4*4=16.

Example 2

Input: [abc,def,ghij,klm]

Output: 12

Explanation: def and ghij do not share any letters, product is 3*4=12.

Example 3

Input: [aa,bb,cc,dd]

Output: 4

Explanation: Any two strings do not share letters, product is 2*2=4.

Example 4

Input: [abc,bcd,cde]

Output: 0

Explanation: All pairs share at least one letter.

Constraints

  • 2 <= len(string_list) <= 1000
  • 1 <= len(s) <= 1000 for each s in string_list
  • Each string in string_list consists only of lowercase English letters
Python (current runtime)

Case 1

Input: ['mnop','qrst','uvwx','yz']

Expected: 16

Case 2

Input: ['a','b','c','d']

Expected: 1

Case 3

Input: ['abc','defg','hijk','lmno']

Expected: 16

Case 4

Input: ['abc','abc','abc']

Expected: 0

Case 5

Input: ['ab','cd','ef','gh']

Expected: 4