LeetCode 318: Maximum Product of Word Lengths Solution
Master LeetCode problem 318 (Maximum Product of Word Lengths), a medium challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.
318. Maximum Product of Word Lengths
Problem Explanation
Explanation
To solve this problem, we can use bit manipulation to represent the presence of letters in a word. We can convert each word into a 26-bit integer where each bit represents the presence of a letter from 'a' to 'z'. By doing this conversion for all words, we can compare each pair of words to check if they have any common letters.
- Convert each word into a 26-bit integer representation.
- Compare each pair of words to check if they have any common letters using bitwise AND operation.
- Calculate the product of the lengths of words that do not share common letters.
- Keep track of the maximum product found.
Time Complexity: O(n^2 * m), where n is the number of words and m is the average length of a word. Space Complexity: O(n)
Solution Code
class Solution {
public int maxProduct(String[] words) {
int n = words.length;
int[] wordBits = new int[n];
for (int i = 0; i < n; i++) {
for (char c : words[i].toCharArray()) {
wordBits[i] |= 1 << (c - 'a');
}
}
int maxProduct = 0;
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
if ((wordBits[i] & wordBits[j]) == 0) {
maxProduct = Math.max(maxProduct, words[i].length() * words[j].length());
}
}
}
return maxProduct;
}
}Try It Yourself
Loading code editor...
Related LeetCode Problems
Frequently Asked Questions
How to solve LeetCode 318 (Maximum Product of Word Lengths)?
This page provides optimized solutions for LeetCode problem 318 (Maximum Product of Word Lengths) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.
What is the time complexity of LeetCode 318 (Maximum Product of Word Lengths)?
The time complexity for LeetCode 318 (Maximum Product of Word Lengths) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.
Can I run code for LeetCode 318 on DevExCode?
Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 318 in Java, C++, or Python.