318. Maximum Product of Word Lengths LeetCode Solution
In this guide, you will get 318. Maximum Product of Word Lengths LeetCode Solution with the best time and space complexity. The solution to Maximum Product of Word Lengths problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Problem Statement of 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.
Complexity Analysis
Time Complexity: O(n^2)
Space Complexity: O(n)
318. Maximum Product of Word Lengths LeetCode Solution in 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;
}
}; /* code provided by PROGIEZ */
318. Maximum Product of Word Lengths LeetCode Solution in Java
class Solution {
public int maxProduct(String[] words) {
int ans = 0;
int[] masks = new int[words.length]; // "abd" -> 0b1011
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;
}
} // code provided by PROGIEZ
318. Maximum Product of Word Lengths LeetCode Solution in 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 << string.ascii_lowercase.index(c)
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 # code by PROGIEZ
