{x}
blog image

Maximum Product of Word Lengths

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.

318. Maximum Product of Word Lengths

Problem Description

Given an array of strings words, find the maximum product of the lengths of two words that do not share any common letters. If no such pair exists, return 0.

Solution Approach

The most efficient approach uses bit manipulation to represent each word as a bitmask. Each bit in the bitmask corresponds to a letter of the alphabet (a-z). If a word contains a letter, the corresponding bit is set to 1; otherwise, it's 0.

Two words share no common letters if and only if their bitwise AND operation results in 0. We can iterate through the words, calculating their bitmasks and checking for pairs with a bitwise AND of 0. The maximum product of lengths is then updated accordingly.

Time and Space Complexity Analysis

  • Time Complexity: O(N^2 + L), where N is the number of words and L is the total number of characters across all words. The nested loops contribute O(N^2), and character processing contributes O(L).
  • Space Complexity: O(N), for storing the bitmasks of each word.

Code Implementation in Multiple Languages

Python3

class Solution:
    def maxProduct(self, words: List[str]) -> int:
        masks = []
        for word in words:
            mask = 0
            for char in word:
                mask |= 1 << (ord(char) - ord('a'))
            masks.append(mask)
 
        max_product = 0
        for i in range(len(words)):
            for j in range(i + 1, len(words)):
                if (masks[i] & masks[j]) == 0:
                    max_product = max(max_product, len(words[i]) * len(words[j]))
        return max_product

Java

class Solution {
    public int maxProduct(String[] words) {
        int[] masks = new int[words.length];
        for (int i = 0; i < words.length; i++) {
            for (char c : words[i].toCharArray()) {
                masks[i] |= 1 << (c - 'a');
            }
        }
 
        int maxProduct = 0;
        for (int i = 0; i < words.length; i++) {
            for (int j = i + 1; j < words.length; j++) {
                if ((masks[i] & masks[j]) == 0) {
                    maxProduct = Math.max(maxProduct, words[i].length() * words[j].length());
                }
            }
        }
        return maxProduct;
    }
}

C++

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

Go

func maxProduct(words []string) int {
	masks := make([]int, len(words))
	for i, word := range words {
		for _, char := range word {
			masks[i] |= 1 << (char - 'a')
		}
	}
 
	maxProduct := 0
	for i := 0; i < len(words); i++ {
		for j := i + 1; j < len(words); j++ {
			if (masks[i] & masks[j]) == 0 {
				maxProduct = max(maxProduct, len(words[i])*len(words[j]))
			}
		}
	}
	return maxProduct
}
 
func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

JavaScript

/**
 * @param {string[]} words
 * @return {number}
 */
var maxProduct = function(words) {
    const masks = words.map(word => {
        let mask = 0;
        for (let char of word) {
            mask |= 1 << (char.charCodeAt(0) - 'a'.charCodeAt(0));
        }
        return mask;
    });
 
    let maxProduct = 0;
    for (let i = 0; i < words.length; i++) {
        for (let j = i + 1; j < words.length; j++) {
            if ((masks[i] & masks[j]) === 0) {
                maxProduct = Math.max(maxProduct, words[i].length * words[j].length);
            }
        }
    }
    return maxProduct;
};

These code examples all follow the same bit manipulation strategy to achieve an efficient solution to the problem. Remember to handle edge cases like empty input arrays appropriately in a production setting.