# Maximum product of word lengths in Python

Problems was to calculate maximum product of word lengths:

Given a string array words, find the maximum value of length(word[i]) * length(word[j]) where the two words do not share common letters. You may assume that each word will contain only lower case letters. If no such two words exist, return 0.

Given ["abcw", "baz", "foo", "bar", "xtfn", "abcdef"]
Return 16
The two words can be "abcw", "xtfn".

Example 2:
Given ["a", "ab", "abc", "d", "cd", "bcd", "abcd"]
Return 4
The two words can be "ab", "cd".

Example 3:
Given ["a", "aa", "aaa", "aaaa"]
Return 0


My answer is correct and passed all the test cases. I am looking to get some code review on this.

class Solution(object):
def maxProduct(self, words):
"""
maximum value of length(word[i]) * length(word[j]) where the two words do not share common letters
>> maxProduct(["eae", "ea", "aaf", "bda", "fcf", "dc", "ac", "ce", "cefde", "dabae"])
>> 15
"""
max_product = 0
words = sorted(words, key=len, reverse=True)
for index, j in enumerate(words):
for i in words[index + 1:]:
count = 0
for k in i:
if k in j:
count = 1
break
if not count:
m = len(j)
n = len(i)
word_product = m * n
if ((m == n) or (m > n and n == m - 1)) and word_product > max_product:
return word_product
if word_product > max_product:
max_product = word_product
return max_product


My solution is quite different, let me explain it:

At first I define a small helper to check if two words have any letter in common, it may also be in-lined, but I like small functions.

def common(a, b):
"""
>>> common("hello", "hi")
{'h'}
"""
return set(a) & set(b)


Then I define the relevant score function for the strings, as you see, after defining our criteria we are almost done.

def product_score(w1, w2):
"""
>>> product_score("foo", "bar")
9
>>> product_score("foo", "fuu")
0
"""
return 0 if common(w1, w2) else len(w1) * len(w2)


The last step is very easy. We already know the criteria, so we can just map it over the combination of 2 of the input list and take the max:

def maxProduct(words):
"""
Maximum value of length(word[i]) * length(word[j]) where the two words do not share common letters.

>>> maxProduct(["eae", "ea", "aaf", "bda", "fcf", "dc", "ac", "ce", "cefde", "dabae"])
15
"""
return max(product_score(w1, w2)
for (w1, w2) in itertools.combinations(words, 2))


I think my solution is more readable, mainly because it uses smaller functions and because it uses already existing wheels (standard library modules).

• I think you want 0 for the common letters case to handle the example. – Barry Dec 30 '15 at 0:15
• The OP processes the words in reverse order by length, which allows early exit when no further improvement is possible. I don't see this feature in your proposed solution. – Gareth Rees Dec 30 '15 at 11:55
• @GarethRees Yes, but he uses N log N time at first for sorting. So the early abort possibility has a cost. Only benchmarking can tell us which solution is more efficient. – Caridorc Dec 30 '15 at 12:41
• When you say "more efficient", do you mean "faster"? – Gareth Rees Dec 30 '15 at 14:05
• @GarethRees yes, I meant run-time efficiency – Caridorc Dec 30 '15 at 14:05

### Avoid introducing so many variables

We have a ton of variables here: index, i, j, k, m, and n. They're all semi-important, and who knows what they mean. Try to avoid this proliferation. We can use itertools.combinations to pairwise iterate to avoid your top two loops:

for w1, w2 in itertools.combinations(words, 2):
...


We can introduce a new function to check that the words are disjoint:

def disjoint_words(a, b):
return not (set(a) & set(b))

for w1, w2 in itertools.combinations(words, 2):
if disjoint_words(w1, w2):
...


And then just use len when doing the lengths:

def maxProduct(words):
max_product = 0
words = sorted(words, key=len, reverse=True)
for w1, w2 in itertools.combinations(words, 2):
if disjoint_words(w1, w2):
cur = len(w1) * len(w2)
if (len(w1) in (len(w2), len(w2) + 1) and
cur > max_product):
return cur
max_product = max(cur, max_product)
return max_product


This is a lot more manageable.

• What happened to all the comments? – python Dec 30 '15 at 0:13
• In addition to there being a lot of variables, they could also be better names (why is j the outer loop variable and i the inner, which isn't idiomatic in any language community afaik? why does j correspond to m and i to n, which swaps the alphabetic order of characters? i and j are also more commonly used for integer loop variables, and I don't think most people would expect to see them used for strings) – Hammerite Dec 31 '15 at 19:00