Course4all
Join us on telegram
Home/dsa/Bit Manipulation/Maximum Product of Word Lengths

Maximum Product of Word Lengths

Master this topic with zero to advance depth.

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.

Medium

Examples

Input: words = ["abcw","baz","foo","bar","xtfn","abcdef"]
Output: 16
Approach 1

Level I: Brute Force (Check All Pairs)

Intuition

Iterate through every pair of words and check if they have common characters using a helper function.

Thought Process

  1. Nested loop (i,j)(i, j) for all pairs.
  2. For each pair:
    • Check overlap: For char in word[i], is it in word[j]?
    • If no overlap, update maxProd.

Pattern: Double Iteration

⏱ O(N^2 \cdot L) - Where $N$ is number of words and $L$ is max word length.💾 O(1) - Assuming constant alphabet space.
java
public class Solution {
    public int maxProduct(String[] words) {
        int max = 0, n = words.length;
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                if (!hasCommon(words[i], words[j])) {
                    max = Math.max(max, words[i].length() * words[j].length());
                }
            }
        }
        return max;
    }
    
    private boolean hasCommon(String s1, String s2) {
        boolean[] set = new boolean[26];
        for (char c : s1.toCharArray()) set[c - 'a'] = true;
        for (char c : s2.toCharArray()) if (set[c - 'a']) return true;
        return false;
    }
}
Approach 2

Level II: Precomputed Sets

Intuition

For each word, precompute a set of its characters. When comparing two words, check if their character sets have any intersection. This is faster than a raw character-by-character check but slower than bitmasking.

⏱ $O(N^2 + N \cdot L)$💾 $O(N \cdot 26)$
java
class Solution {
    public int maxProduct(String[] words) {
        int n = words.length;
        boolean[][] has = new boolean[n][26];
        for (int i = 0; i < n; i++) {
            for (char c : words[i].toCharArray()) has[i][c - 'a'] = true;
        }
        int maxP = 0;
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                boolean common = false;
                for (int k = 0; k < 26; k++) {
                    if (has[i][k] && has[j][k]) { common = true; break; }
                }
                if (!common) maxP = Math.max(maxP, words[i].length() * words[j].length());
            }
        }
        return maxP;
    }
}
Approach 3

Level III: Optimal (Bitmasking)

Intuition

Each word can be represented by a 26-bit integer (bitmask). Two words share NO common letters if and only if their bitwise AND is 0.

Thought Process

  1. Precompute bitmasks for all words.
  2. Nested loop (i,j)(i, j) and check (masks[i] & masks[j]) == 0.
  3. Update max product.

Pattern: Alphabet Bitmasking

⏱ O(N^2 + N \cdot L) - $O(N \cdot L)$ to build masks, $O(N^2)$ to compare pairs.💾 O(N) - To store the bitmasks.

Detailed Dry Run

"abcw" -> mask = 0x400007 "xtfn" -> mask = 0x882020 mask1 & mask2 = 0. Product = 4 * 4 = 16.

java
public class Solution {
    public int maxProduct(String[] words) {
        int n = words.length;
        int[] masks = new int[n];
        for (int i = 0; i < n; i++) {
            for (char c : words[i].toCharArray()) {
                masks[i] |= (1 << (c - 'a'));
            }
        }
        int maxP = 0;
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                if ((masks[i] & masks[j]) == 0) {
                    maxP = Math.max(maxP, words[i].length() * words[j].length());
                }
            }
        }
        return maxP;
    }
}
← Previous QuestionRepeated DNA Sequences
Next Question →Maximum XOR of Two Numbers in an Array