• Posts

Problem 318 Maximum Product of Word Lengths

Problem Statement

Link - Problem 318

Question

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.

Solution

class Solution {
public:
    int maxProduct(vector<string>& words) {
        ios_base::sync_with_stdio(false);
        cin.tie(NULL);
        cout.tie(NULL);
        int size = words.size();
        vector<int> nums;
        for (int index = 0; index < size; index++) {
            int num = 0;
            for (char c : words[index]) {
                num |= 1 << (c - 'a');
            }
            nums.push_back(num);
        }
        int maxProd = 0;
        for (int index = 0; index < size; index++) {
            for (int index2 = index + 1; index2 < size; index2++) {
                if ((nums[index] & nums[index2]) == 0) {
                    maxProd = max(maxProd, (int)words[index].length() * (int)words[index2].length());
                }
            }
        }
        return maxProd;
    }
};

Complexity Analysis

| Algorithm                    | Time Complexity | Space Complexity |
| ---------------------------- | --------------- | ---------------- |
| Bitmasking with Nested Loops | O((n^2)m)       | O(n)             |

Explanation

Intial Thoughts

To solve this problem, we should first think about how to efficiently compare words to find those without common letters. We can represent each word as a unique set of letters or a bitmask. Then, we should consider how to optimize the comparison process, perhaps using a strategy that minimizes the number of word pairs to compare. Additionally, we need to keep track of the maximum product of word lengths found so far. Lastly, we must ensure the comparison is case-sensitive as per the problem constraints, but since the problem only involves lowercase letters, this simplifies our approach.

Intuitive Analysis

An intuitive approach involves recognizing the bitwise operations can efficiently represent and compare the letters in each word. By converting each word into a bitmask where each bit corresponds to the presence of a letter in the alphabet, we can use bitwise AND to check for common letters between two words. If the result is zero, it means the words do not share any letters. We should also consider sorting the words by their lengths in descending order to prioritize comparisons between longer words, which could lead to a larger product. Lastly, maintaining a running maximum of the product of word lengths as we compare pairs of words allows us to efficiently find the solution.

1. Intuition

• The problem requires finding two words in the given array that do not share common letters and have the maximum product of their lengths.
• To efficiently solve this problem, we need to think about how to represent each word in a way that allows us to quickly check for common letters.
• Using a bitmask to represent each word is a good approach, where each bit corresponds to a letter in the alphabet.
• This approach works because it allows us to use bitwise operations to check for common letters between two words.
• The key insight is that if the bitwise AND of two words’ bitmasks is zero, then the two words do not share any common letters.
• This solution works because it has a time complexity of O(n^2 * m), where n is the number of words and m is the maximum length of a word.
• The algorithmic choice of using two nested loops to compare each pair of words is necessary to find the maximum product of lengths.

2. Implementation

• We start by creating a vector nums to store the bitmask for each word, where num is calculated using num |= 1 << (c - 'a') for each character c in the word.
• We then initialize maxProd to zero, which will store the maximum product of lengths found so far.
• The outer loop iterates over each word in the array, and the inner loop iterates over each word that comes after it in the array.
• Inside the inner loop, we check if the bitwise AND of the current word’s bitmask and the compared word’s bitmask is zero using (nums[index] & nums[index2]) == 0.
• If the bitwise AND is zero, we update maxProd with the maximum of its current value and the product of the lengths of the current word and the compared word using max(maxProd, (int)words[index].length() * (int)words[index2].length()).
• Finally, we return maxProd as the result, which is the maximum product of lengths of two words that do not share common letters.
• The use of ios_base::sync_with_stdio(false) and cin.tie(NULL) is for optimization purposes to improve the performance of the input/output operations.

Complexity Analysis

Time Complexity:

• The code has two nested loops that run in O(n^2) time complexity, where n is the number of words in the input vector words. For each word, it calculates a bitmask in O(m) time, where m is the maximum length of a word.
• The dominant operations are the two nested loops and the calculation of the bitmask, resulting in a total time complexity of O(n^2 * m).
• To justify the Big O classification, we consider the worst-case scenario where all words have the maximum length, resulting in n^2 comparisons and n * m bitmask calculations, hence O(n^2 * m).

Space Complexity:

• The code uses a vector nums to store the bitmask of each word, resulting in a space complexity of O(n), where n is the number of words.
• The data structure impact is primarily due to the nums vector and the input vector words, which requires O(n * m) space to store all the words, but the bitmask calculation only requires O(n) space.
• The justification of space complexity lies in the fact that the input vector words and the nums vector require a linear amount of space with respect to the number of words, hence O(n).

Footnote

This question is rated as Medium difficulty.