grid47 Exploring patterns and algorithms
Oct 6, 2024
5 min read
Solution to LeetCode 318: Maximum Product of Word Lengths Problem
Given a list of words, return the maximum product of lengths of two words such that the two words do not share common letters. If no such pair exists, return 0.
Problem
Approach
Steps
Complexity
Input: The input is a list of words, where each word consists of lowercase English letters.
Example: words = ["abc", "xyz", "foo", "bar", "pqr", "abcdef"]
Constraints:
• 2 <= words.length <= 1000
• 1 <= words[i].length <= 1000
• words[i] consists of lowercase English letters
Output: Return the maximum product of lengths of two words that do not share common letters.
Example: 15
Constraints:
• If no such pair exists, return 0.
Goal: To find the maximum product of lengths of two words where the words do not share any common letters.
Steps:
• For each word, calculate its bitmask where each bit represents whether a letter is present in the word.
• For each pair of words, check if the bitmasks do not overlap (i.e., they share no common letters).
• Calculate the product of the lengths of words that do not share any common letters, and track the maximum product.
Goal: The solution should handle a large number of words and word lengths efficiently.
Steps:
• Ensure that the solution works efficiently for strings up to 1000 characters and up to 1000 words.
Assumptions:
• The words are non-empty and consist of lowercase English letters.
• Input: words = ["abc", "xyz", "foo", "bar", "pqr", "abcdef"]
• Explanation: The two words with no common letters are 'abc' and 'xyz'. The product of their lengths is 15, which is the maximum.
• Input: words = ["a", "ab", "ac", "b", "bc"]
• Explanation: The maximum product is 2, obtained by the words 'a' and 'bc'.
Approach: Use bitmasking to represent the letters in each word, and calculate the maximum product of lengths of words that do not share common letters.
Observations:
• Each word can be represented by a bitmask, where each bit represents a character.
• We can compare two words by checking if their bitmasks have no common bits set, indicating no common letters.
Steps:
• For each word, compute the bitmask representing the presence of each letter.
• Iterate through all pairs of words, comparing their bitmasks. If the bitmasks do not overlap, compute their length product.
• Track the maximum length product found during the iteration.
Empty Inputs:
• The problem guarantees at least two words in the input.
Large Inputs:
• The solution must efficiently handle up to 1000 words, each with a length up to 1000.
Special Values:
• If no words share no common letters, the answer should be 0.
Constraints:
• Ensure the solution has a time complexity of O(n^2) or better to handle the problem's input size.
intmaxProduct(vector<string>& words) {
int len = words.size();
vector<int> mask(len, 0);
int res =0;
for(int i =0; i < len; i++) {
string word = words[i];
int sz = word.size();
for(int j =0; j < sz; j++)
mask[i] |= (1<< (word[j] -'a'));
for(int j =0; j < i; j++) {
if((mask[i] & mask[j]) ==0)
res = max(res, int (words[i].size() * words[j].size() ));
}
}
return res;
}
1 : Function Declaration
intmaxProduct(vector<string>& words) {
The function `maxProduct` accepts a vector of strings `words` as input and returns an integer representing the maximum product of lengths of two words that do not share common characters.
2 : Variable Initialization
int len = words.size();
This line initializes `len` to hold the number of words in the vector.
3 : Variable Initialization
vector<int> mask(len, 0);
A vector `mask` of integers is initialized, where each element corresponds to a word in the input and will hold a bitmask of the characters in that word.
4 : Variable Initialization
int res =0;
The variable `res` is initialized to store the maximum product of lengths found during the iteration.
5 : Iteration
for(int i =0; i < len; i++) {
A loop is started to iterate over each word in the `words` vector.
6 : Variable Declaration
string word = words[i];
For each iteration, the word at index `i` is extracted and stored in the variable `word`.
7 : Variable Declaration
int sz = word.size();
The variable `sz` stores the length of the current word to assist with looping over its characters.
8 : Looping
for(int j =0; j < sz; j++)
This inner loop iterates over each character of the current word.
9 : Bit Manipulation
mask[i] |= (1<< (word[j] -'a'));
For each character, the corresponding bit in the `mask[i]` is set to 1. This represents the characters present in the word using a bitmask.
10 : Iteration
for(int j =0; j < i; j++) {
This loop compares the bitmask of the current word `i` with the words before it.
11 : Bitwise Operation
if((mask[i] & mask[j]) ==0)
This condition checks whether the two words `i` and `j` share any common characters using a bitwise AND operation.
12 : Max Calculation
res = max(res, int (words[i].size() * words[j].size() ));
If the words do not share any characters, the product of their lengths is calculated and stored in `res` if it is the maximum product found so far.
13 : Return
return res;
The function returns the maximum product of word lengths found.
Best Case: O(n^2)
Average Case: O(n^2)
Worst Case: O(n^2)
Description: The time complexity is O(n^2) due to comparing each word with every other word.
Best Case: O(n)
Worst Case: O(n)
Description: The space complexity is O(n) for storing the bitmasks of the words.
