algoadvance

Leetcode 318. Maximum Product of Word Lengths

Problem Statement

You are given an array of strings words. Each word consists of lowercase English letters.

Your task is to find the maximum value of length(word[i]) * length(word[j]) where the two words do not share common letters.

Clarifying Questions

  1. Input Size: What is the maximum size of the words array, and what is the maximum length of an individual word?
    • Typically for LeetCode problems, the assumption can be hundreds to thousands of words, each up to 100 characters long.
  2. Character Set: Do the words contain only lowercase English letters?
    • Yes, each word consists of lowercase English letters only.
  3. Empty Array: Should we consider the case when the input array is empty?
    • Usually, yes. In this case, the maximum product should be 0.
  4. Output: Should the function return an integer representing the maximum product?
    • Yes, the function should return the maximum product as an integer.

Strategy

  1. Bitmask Representation:
    • Use a bitmask to represent each word’s unique character set. Each bit in an integer (32-bit) can represent if a letter ‘a’ to ‘z’ is present (1) or not (0).
  2. Precomputation:
    • Precompute a bitmask for each word.
  3. Pairwise Comparison:
    • Compare each pair of words to ensure they do not share common letters using the bitmask.
  4. Calculate Product:
    • Calculate the product of the lengths of two words if they do not share common letters and keep track of the maximum product.

Code

#include <vector>
#include <string>
#include <algorithm>

int maxProduct(std::vector<std::string>& words) {
    int n = words.size();
    if (n == 0) return 0;
    
    // Step 1: Convert words to bitmasks
    std::vector<int> bitmasks(n, 0);
    for (size_t i = 0; i < n; ++i) {
        for (char c : words[i]) {
            bitmasks[i] |= 1 << (c - 'a');
        }
    }
    
    // Step 2: Find max product of lengths of pairs of different words without common letters
    int max_prod = 0;
    for (size_t i = 0; i < n; ++i) {
        for (size_t j = i + 1; j < n; ++j) {
            if ((bitmasks[i] & bitmasks[j]) == 0) {
                int prod = words[i].length() * words[j].length();
                max_prod = std::max(max_prod, prod);
            }
        }
    }
    
    return max_prod;
}

Time Complexity

Therefore, the overall time complexity is O(N^2 + N * L), which simplifies to O(N^2) for pairs comparison in practice, as L is relatively small compared to N.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI