algoadvance

Leetcode 318. Maximum Product of Word Lengths

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.

Clarifying Questions

  1. Input Size: What is the maximum length of the array words and the maximum length of each word?
    • Usually, we expect words.length to be up to 10^3 and the length of each word up to 10^3, but we should confirm.
  2. Character Set: Are the words composed of only lowercase English letters?
    • Assuming from typical constraints, yes.
  3. Output: Are we guaranteed that there will be at least two words in the array?
    • If not, we should handle cases where there are fewer than two words by directly returning 0.

Strategy

  1. Bitmask Representation:
    • Each word can be represented by a bitmask with 26 bits, where each bit corresponds to a character ‘a’ to ‘z’. For example, if a word contains ‘a’, ‘b’, and ‘c’, then its bitmask will have the first three bits set (i.e., 000...0111).
  2. Store Lengths and Bitmasks:
    • We will create an array of the same length as words where each element contains the bitmask of the word and its length.
  3. Check Pairwise:
    • Iterate over all pairs of words, checking if their bitmasks do not overlap. If not overlapping, calculate the product of their lengths and keep track of the maximum product.

Code

import java.util.*;

public class Solution {
    public int maxProduct(String[] words) {
        if (words.length < 2) {
            return 0;
        }
        
        int n = words.length;
        int[] masks = new int[n];
        int[] lengths = new int[n];
        
        for (int i = 0; i < n; i++) {
            int bitmask = 0;
            for (char c : words[i].toCharArray()) {
                bitmask |= (1 << (c - 'a'));
            }
            masks[i] = bitmask;
            lengths[i] = words[i].length();
        }
        
        int maxProduct = 0;

        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                if ((masks[i] & masks[j]) == 0) {
                    maxProduct = Math.max(maxProduct, lengths[i] * lengths[j]);
                }
            }
        }

        return maxProduct;
    }
}

Time Complexity

Thus, the total time complexity is O(N * L + N^2).

This approach ensures that the solution is efficient given usual constraints, but keep in mind that for extremely large inputs, the quadratic part (N^2) might become a bottleneck.

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