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.
Example 1:
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
No such pair of words.
Credits:
Special thanks to @dietpepsi for adding this problem and creating all test cases.
Subscribe to see which companies asked this question
class Solution(object):
def maxProduct(self, words):
bits_words = [reduce(lambda s,x: s|(1<<ord(x)-ord('a')), w, 0) for w in words]
ans = 0
for i, word in enumerate(words):
for j in range(i+1, len(words)):
if len(word)*len(words[j]) > ans and self.has_diff(bits_words[i], bits_words[j]):
ans = len(word)*len(words[j])
return ans def has_diff(self, w1, w2):
return (w1&w2) == 0