Maximum Product of Word Lengths LeetCode Solution

Last updated on October 5th, 2024 at 09:26 pm

Here, We see Maximum Product of Word Lengths LeetCode Solution. This Leetcode problem is done in many programming languages like C++, Java, JavaScript, Python, etc. with different approaches.

List of all LeetCode Solution

Topics

Bit Manipulation

Companies

Google

Level of Question

Medium

Maximum Product of Word Lengths LeetCode Solution

Maximum Product of Word Lengths LeetCode Solution

Problem Statement

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.

1. Maximum Product of Word Lengths Leetcode Solution C++

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

2. Maximum Product of Word Lengths Leetcode Solution Java

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

3. Maximum Product of Word Lengths Solution JavaScript

var maxProduct = function(words) {
    words.sort((a,b) => b.length - a.length)
    let best = 0, bitsets = new Uint32Array(words.length)
    for (let i = 0; i < words.length; i++) {
        let word = words[i], wlen = word.length, bitset = 0
        if (wlen * words[0].length < best)
            return best
        for (let j = 0; j < wlen; j++)
            bitset |= 1 << (word.charCodeAt(j) - 97)
        for (let j = 0; j < i; j++)
            if ((bitsets[j] & bitset) === 0)
                best = Math.max(best, wlen * words[j].length)
        bitsets[i] = bitset
    }
    return best
};

4. Maximum Product of Word Lengths Solution Python

class Solution(object):
    def maxProduct(self, words):
        words.sort(key=len, reverse=True)
        best, bitsets = 0, {}
        for i in range(len(words)):
            wlen, bitset = len(words[i]), 0
            if wlen * len(words[0]) < best:
                return best
            for c in words[i]:
                bitset |= 1 << ord(c) - 97
            if bitset not in bitsets:
                for k,v in bitsets.items():
                    if not bitset & k:
                        best = max(best, wlen * v)
                bitsets[bitset] = wlen
        return best
Scroll to Top