318. Maximum Product of Word Lengths – Leetcode Solutions

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.

class Solution:
    def maxProduct(self, words: List[str]) -> int:
        # Step 1: Create a list of bitmasks for each word
        n = len(words)
        bitmasks = [0] * n  # Store bitmask for each word
        lengths = [0] * n   # Store the length of each word

        for i, word in enumerate(words):
            bitmask = 0
            for char in word:
                # Set the bit corresponding to the character
                bitmask |= 1 << (ord(char) - ord('a'))
            bitmasks[i] = bitmask
            lengths[i] = len(word)

        # Step 2: Compare all pairs of words and calculate the maximum product
        max_product = 0
        for i in range(n):
            for j in range(i + 1, n):
                # If two words do not share common letters, their bitmasks AND result will be 0
                if bitmasks[i] & bitmasks[j] == 0:
                    max_product = max(max_product, lengths[i] * lengths[j])

        return max_product

#include <vector>
#include <string>
#include <bitset>
using namespace std;

class Solution {
public:
    // Function to calculate the maximum product of lengths of two words without common letters
    int maxProduct(vector<string>& words) {
        int n = words.size(); // Number of words
        vector<int> bitmasks(n, 0); // Vector to store bitmasks for each word
        
        // Loop through each word and calculate its bitmask
        for (int i = 0; i < n; ++i) {
            for (char c : words[i]) {
                // Set the corresponding bit for each character in the word
                bitmasks[i] |= (1 << (c - 'a'));
            }
        }
        
        int maxProduct = 0; // Variable to store the maximum product
        
        // Compare every pair of words
        for (int i = 0; i < n; ++i) {
            for (int j = i + 1; j < n; ++j) {
                // Check if the two words do not share any common letters
                if ((bitmasks[i] & bitmasks[j]) == 0) {
                    // Calculate the product of lengths if no common letters are found
                    int product = words[i].length() * words[j].length();
                    // Update the maximum product if current product is larger
                    maxProduct = max(maxProduct, product);
                }
            }
        }
        
        return maxProduct; // Return the maximum product
    }
};

var maxProduct = function(words) {
    // Step 1: Create an array to store the bit representation of each word.
    let bitMasks = new Array(words.length).fill(0);
    
    // Step 2: Fill the bitMasks array with the bit representation of each word.
    for (let i = 0; i < words.length; i++) {
        let bitmask = 0;
        for (let char of words[i]) {
            // Set the bit corresponding to the character 'char'
            bitmask |= (1 << (char.charCodeAt(0) - 'a'.charCodeAt(0)));
        }
        bitMasks[i] = bitmask;
    }

    // Step 3: Initialize a variable to track the maximum product found.
    let maxProduct = 0;

    // Step 4: Compare each pair of words.
    for (let i = 0; i < words.length; i++) {
        for (let j = i + 1; j < words.length; j++) {
            // Check if words[i] and words[j] share common letters
            if ((bitMasks[i] & bitMasks[j]) === 0) { // No common letters
                // Calculate product of their lengths
                let product = words[i].length * words[j].length;
                // Update maxProduct if this product is greater than the current maxProduct
                maxProduct = Math.max(maxProduct, product);
            }
        }
    }

    // Step 5: Return the maximum product found
    return maxProduct;
};

class Solution {
    public int maxProduct(String[] words) {
        // Step 1: Get the number of words
        int n = words.length;
        
        // Step 2: Create an array to store bitmasks for each word
        int[] bitMasks = new int[n];
        
        // Step 3: Fill the bitMasks array
        for (int i = 0; i < n; i++) {
            int bitMask = 0;  // Initialize the bitmask for the current word
            for (char c : words[i].toCharArray()) {
                // Set the bit corresponding to the character 'c' in the bitmask
                bitMask |= 1 << (c - 'a');  // 'a' corresponds to the 0th bit, 'b' to 1st bit, etc.
            }
            bitMasks[i] = bitMask;  // Store the computed bitmask for the current word
        }
        
        // Step 4: Initialize variable to store the maximum product of lengths
        int maxProduct = 0;
        
        // Step 5: Compare every pair of words
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                // Step 6: Check if two words share any common letters using bitmask comparison
                if ((bitMasks[i] & bitMasks[j]) == 0) {
                    // No common letters, calculate the product of their lengths
                    int product = words[i].length() * words[j].length();
                    // Update maxProduct if the current product is larger
                    maxProduct = Math.max(maxProduct, product);
                }
            }
        }
        
        // Step 7: Return the maximum product found
        return maxProduct;
    }
}