Maximum Product Of Word Lengths Problem
Description
LeetCode Problem 318.
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:
1
2
3
Input: words = ["abcw","baz","foo","bar","xtfn","abcdef"]
Output: 16
Explanation: The two words can be "abcw", "xtfn".
Example 2:
1
2
3
Input: words = ["a","ab","abc","d","cd","bcd","abcd"]
Output: 4
Explanation: The two words can be "ab", "cd".
Example 3:
1
2
3
Input: words = ["a","aa","aaa","aaaa"]
Output: 0
Explanation: No such pair of words.
Constraints:
- 2 <= words.length <= 1000
- 1 <= words[i].length <= 1000
- words[i] consists only of lowercase English letters.
Sample C++ Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
int maxProduct(vector<string>& words) {
vector<int> mask(words.size());
int result = 0;
for (int i=0; i<words.size(); ++i) {
for (char c : words[i])
mask[i] |= 1 << (c - 'a');
for (int j=0; j<i; ++j)
if (!(mask[i] & mask[j]))
result = max(result, int(words[i].size() * words[j].size()));
}
return result;
}
};