Maximum Product Of Word Lengths - Leetcode Solution

Problem Description:

Given a string array words, find the maximum value of length(word[i]) * length(word[j]) where the two words do not share common letters. You may assume that each word will contain only lower case letters. If no such two words exist, return 0.

Solution:

Approach:

1. Intuition: As we need to multiply the lengths of two different words in which no two letters are common, we can assume each letter of the word to be present or not in a boolean array of size 26(since we are assuming all words to be of lowercase letters). We can traverse the array and check for each word pair if any letter is common and if it is not then we can calculate product length*length and update our max accordingly.
2. Brute force solution: We can iterate the array for each pair in the array and check if the two words share common information or not. We can store the lengths of words in an array and then take the max.

Code:

class Solution { public: int maxProduct(vector<string>& words) { int n = words.size(); vector<int> groups(n); vector<int> mask(n); for (int i = 0; i < n; ++i) { for (char c : words[i]) { mask[i] |= 1 << (c - 'a'); } } int ans = 0; for (int i = 0; i < n; ++i) { for (int j = 0; j < i; ++j) { if ((mask[i] & mask[j]) == 0) { ans = max(ans, int(words[i].size() * words[j].size())); } } } return ans; } };

Explanation:

//Variable Information:

words: vector array of strings n: size of words groups: vector containing length of each word mask: vector containing whether a letter is present in a word or not. ans: variable to keep track of max product

//For each element in the words array, we traverse the string and set the corresponding letter's bit in the mask array to 1. for (int i = 0; i < n; ++i) { for (char c : words[i]) { mask[i] |= 1 << (c - 'a'); } }

//Then we apply nested loop and calculate the max product of the non-overlapping words. for (int i = 0; i < n; ++i) { for (int j = 0; j < i; ++j) { if ((mask[i] & mask[j]) == 0) { ans = max(ans, int(words[i].size() * words[j].size())); } } } return ans;

Complexity Analysis: Time complexity: O(n^2) as we need to traverse each pair of words in the array. Space complexity: O(n^2) as we need to keep the mask to check for common letters.

1