318. Maximum Product of Word Lengths
Medium
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.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.
Constraints:
2 <= words.length <= 10001 <= words[i].length <= 1000words[i]consists only of lowercase English letters.
func maxProduct(words []string) int {
m := make(map[int]int)
ans := 0
for _, word := range words {
mask := 0
for i := 0; i < len(word); i++ {
mask |= 1 << (word[i] - 'a');
}
m[mask] = max(m[mask], len(word))
for k, v := range m {
if mask & k == 0 {
ans = max(ans, len(word) * v)
}
}
}
return ans
}
func max(a, b int) int {
if a > b { return a }
return b
}
Last modified 5mo ago