In this Leetcode Maximum Product of Word Lengths problem solution, You are given a string array of 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.

Leetcode Maximum Product of Word Lengths problem solution


Problem solution in Python.

class Solution(object):

    def maxProduct(self, words):
        """
        :type words: List[str]
        :rtype: int
        """
        word_bit = [0 for _ in range(len(words))]
        maxLen = 0
        for i, word in enumerate(words):
            for c in word:
                mask = 1 << ord(c) - ord('a')
                word_bit[i] |= mask

        for i in range(0, len(words) - 1):
            for j in range(i + 1, len(words)):
                if word_bit[i] & word_bit[j] == 0:
                    maxLen = max(len(words[i]) * len(words[j]), maxLen)

        return maxLen



Problem solution in Java.

public int maxProduct(String[] words) {
    int n = words.length, max = 0;
    int[] mask = new int[n];
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < words[i].length(); j++)
            mask[i] |= 1 << (words[i].charAt(j) - 'a');
        for (int j = 0; j < i; j++)
            if ((mask[j] & mask[i]) == 0)
                max = Math.max(max, words[i].length() * words[j].length());
    }
    return max;
}


Problem solution in C++.

class Solution {
public:
    int maxProduct(vector<string>& words) {
        int res=INT_MIN;
        
        for(int i=0;i<words.size();i++){
           
            for(int j=0;j<words.size() and j!=i;j++){
                if(words[i].find_first_of(words[j])==string::npos){
                    int l=words[i].length()*words[j].length();
                    res=max(res,l);
                }
            }
        }
        return max(res,0);
    }
};


Problem solution in C.

#include <stdlib.h>
#include <string.h>

struct wordData
{
    unsigned int length;
    unsigned int bitMask;
};

int maxProduct(char ** words, int wordsSize){
    int idx, idx2, maxProd = 0;
    struct wordData *pWordData;
    
    pWordData = malloc(sizeof(struct wordData) * wordsSize);
    for (idx = 0; idx < wordsSize; idx++)
    {
        char *pWord;  
        
        pWord = words[idx];
        pWordData[idx].length = 0;
        pWordData[idx].bitMask = 0;
        while ('\0' != *pWord)
        {
            pWordData[idx].length++;
            pWordData[idx].bitMask |= (1 << (*pWord - 'a'));
            pWord++;
        }
    }
    for (idx = 0; idx < wordsSize; idx++)
    {
        for (idx2 = idx + 1; idx2 < wordsSize; idx2++)
        {
            if (0 == (pWordData[idx].bitMask & pWordData[idx2].bitMask))
            {
                int prod;
                
                prod = pWordData[idx].length * pWordData[idx2].length;
                maxProd = (prod > maxProd) ? prod : maxProd;
            }
        }
    }
    
    free(pWordData);
    
    return maxProd;
}