Last updated on January 9th, 2025 at 02:13 am
Here, we see a Maximum Product of Word Lengths LeetCode Solution. This Leetcode problem is solved using different approaches in many programming languages, such as C++, Java, JavaScript, Python, etc.
List of all LeetCode Solution
Topics
Bit Manipulation
Companies
Level of Question
Medium
Maximum Product of Word Lengths LeetCode Solution
Table of Contents
1. Problem Statement
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.
2. Coding Pattern Used in Solution
The coding pattern used in this code is Bit Manipulation. The code leverages bitwise operations to efficiently represent and compare character sets of words, which allows for quick determination of whether two words share common characters.
3. Code Implementation in Different Languages
3.1 Maximum Product of Word Lengths C++
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;
}
};
3.2 Maximum Product of Word Lengths Java
class Solution {
public int maxProduct(String[] words) {
int max = 0;
Arrays.sort(words, new Comparator<String>(){
public int compare(String a, String b){
return b.length() - a.length();
}
});
int[] masks = new int[words.length];
for(int i = 0; i < masks.length; i++){
for(char c: words[i].toCharArray()){
masks[i] |= 1 << (c - 'a');
}
}
for(int i = 0; i < masks.length; i++){
if(words[i].length() * words[i].length() <= max) break;
for(int j = i + 1; j < masks.length; j++){
if((masks[i] & masks[j]) == 0){
max = Math.max(max, words[i].length() * words[j].length());
break;
}
}
}
return max;
}
}
3.3 Maximum Product of Word Lengths JavaScript
var maxProduct = function(words) {
words.sort((a,b) => b.length - a.length)
let best = 0, bitsets = new Uint32Array(words.length)
for (let i = 0; i < words.length; i++) {
let word = words[i], wlen = word.length, bitset = 0
if (wlen * words[0].length < best)
return best
for (let j = 0; j < wlen; j++)
bitset |= 1 << (word.charCodeAt(j) - 97)
for (let j = 0; j < i; j++)
if ((bitsets[j] & bitset) === 0)
best = Math.max(best, wlen * words[j].length)
bitsets[i] = bitset
}
return best
};
3.4 Maximum Product of Word Lengths Python
class Solution(object):
def maxProduct(self, words):
words.sort(key=len, reverse=True)
best, bitsets = 0, {}
for i in range(len(words)):
wlen, bitset = len(words[i]), 0
if wlen * len(words[0]) < best:
return best
for c in words[i]:
bitset |= 1 << ord(c) - 97
if bitset not in bitsets:
for k,v in bitsets.items():
if not bitset & k:
best = max(best, wlen * v)
bitsets[bitset] = wlen
return best
4. Time and Space Complexity
| Time Complexity | Space Complexity | |
| C++ | O(n² + n * k) | O(n) |
| Java | O(n² + n * k + n log n) | O(n) |
| JavaScript | O(n² + n * k + n log n) | O(n) |
| Python | O(n² + n * k + n log n) | O(n) |
where, Sorting is O(n log n), outer loop is O(n), inner loop for pairs is O(n), and bitmask creation is O(k).
- Bit Manipulation is the core optimization here, as it allows for quick checks of shared characters between words.
- Sorting in Java, JavaScript, and Python implementations helps reduce unnecessary comparisons by allowing early termination.
- The time complexity is dominated by the pairwise comparison of words (
O(n²)), while the space complexity is linear (O(n)) due to the storage of bitmasks.