Maximum Product of Word Lengths 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 <= 1000
1 <= words[i].length <= 1000
words[i]
consists only of lowercase English letters.
Maximum Product of Word Lengths Solutions
✅Time: O(n)
✅Space: O(n)
C++
class Solution {
public:
int maxProduct(vector<string>& words) {
size_t ans = 0;
vector<int> masks;
for (const string& word : words)
masks.push_back(getMask(word));
for (int i = 0; i < words.size(); ++i)
for (int j = 0; j < i; ++j)
if ((masks[i] & masks[j]) == 0)
ans = max(ans, words[i].length() * words[j].length());
return ans;
}
private:
int getMask(const string& word) {
int mask = 0;
for (const char c : word)
mask |= 1 << c - 'a';
return mask;
}
};
Java
class Solution {
public int maxProduct(String[] words) {
int ans = 0;
int[] masks = new int[words.length]; // "abd" -> (1011)2
for (int i = 0; i < words.length; ++i)
masks[i] = getMask(words[i]);
for (int i = 0; i < masks.length; ++i)
for (int j = 0; j < i; ++j)
if ((masks[i] & masks[j]) == 0)
ans = Math.max(ans, words[i].length() * words[j].length());
return ans;
}
private int getMask(final String word) {
int mask = 0;
for (final char c : word.toCharArray())
mask |= 1 << c - 'a';
return mask;
}
}
Python
class Solution:
def maxProduct(self, words: List[str]) -> int:
ans = 0
def getMask(word: str) -> int:
mask = 0
for c in word:
mask |= 1 << ord(c) - ord('a')
return mask
masks = [getMask(word) for word in words]
for i in range(len(words)):
for j in range(i):
if not (masks[i] & masks[j]):
ans = max(ans, len(words[i]) * len(words[j]))
return ans
Watch Tutorial
Checkout more Solutions here