Maximum Product of Word Lengths

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: "abcw" and "xtfn" share no common letters, and 4 * 4 = 16.

Example 2

Input: words = ["a","ab","abc","d","cd","bcd","abcd"] Output: 4 Explanation: "abc" and "d" share no letters, 3 * 1 = 3; "ab" and "cd" give 4.

Solution Approach

Represent each word as a bitmask of 26 bits where bit i is set if character 'a'+i appears in the word. Two words share no common letters if and only if the AND of their bitmasks is 0.

Build a bitmask for each word by setting bit (c - 'a') for each character c.
For every pair (i, j), check if mask[i] & mask[j] == 0.
If no common letters, update the maximum with words[i].length() * words[j].length().

Java

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

Complexity Analysis:

Time complexity: O(n^2 + L) where L is total characters across all words.
Space complexity: O(n). For the bitmask array.