318. Maximum Product of Word Lengths
1. Description
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.
2. Example
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.
3. Constraints
- 2 <= words.length <= 1000
- 1 <= words[i].length <= 1000
- words[i] consists only of lowercase English letters.
4. Solutions
Bit Manipulation && Hash && Sort
n = words.size()
Time complexity: O($n^2$)
Space complexity: O(n)
class Solution {
public:
int maxProduct(const vector<string> &words) {
unordered_map<int, int> wordbit_length;
for (const auto &word : words) {
int word_bit = 0;
for (const auto &letter : word) {
word_bit |= 1 << (letter - 'a');
}
if (word.size() > wordbit_length[word_bit]) {
wordbit_length[word_bit] = word.size();
}
}
vector<pair<int, int>> items(wordbit_length.begin(), wordbit_length.end());
sort(items.begin(), items.end(), [](const pair<int, int> &a, const pair<int, int> &b) {
return a.second > b.second;
});
int max_product = 0;
for (int i = 0; i < items.size(); ++i) {
if (items[i].second * items[i].second <= max_product) {
break;
}
for (int j = i + 1; j < items.size(); ++j) {
if ((items[i].first & items[j].first) == 0) {
max_product = max(items[i].second * items[j].second, max_product);
break;
}
if (items[i].second * items[j].second <= max_product) {
break;
}
}
}
return max_product;
}
};