---

1. Problem Summary

You are given an array of strings words.

Your task is to find the maximum value of:

length(wordA) * length(wordB)

where:

• wordA and wordB share no common letters
• letters are lowercase English a–z
• order does not matter
• if no such pair exists, return 0

Example:

words = ["abcw","baz","foo","bar","xtfn","abcdef"]

Valid pair:

"abcw" and "xtfn"

Lengths:

4 * 4 = 16

Output:

16

---

2. Key Insights

Insight 1: Checking shared letters directly is too slow

Naive comparison of characters between every pair is:

O(N² * L)

Where L = max word length.

Insight 2: Letters can be encoded in a 26-bit integer

Since words use only lowercase English letters, we can create a bitmask:

bit i = 1 if letter 'a' + i appears in word

Example:

"abc" → 00000000000000000000000111
"dog" → bits for d, o, g

Insight 3: Two words have no common letters if:

(maskA & maskB) == 0

Insight 4: Store both mask and word length

Then checking pairs is very fast.

---

3. Approach

Preprocess words into bitmasks, then compare pairs

Steps:

1. Initialize an integer array masks
2. Initialize an integer array lengths
3. For each word:
   • compute bitmask
   • store mask and word length
4. Initialize maxProduct = 0
5. For each pair (i,j):
   • if (masks[i] & masks[j]) == 0:
     compute product
     update maxProduct
6. Return maxProduct

---

4. Time and Space Complexity

Time Complexity:

O(N²)

Comparing masks is O(1), so pairwise check dominates.

Space Complexity:

O(N)

To store masks and lengths.

---

5. Java Solution

class Solution {
    public int maxProduct(String[] words) {
        int n = words.length;
        int[] masks = new int[n];
        int[] lengths = new int[n];

        for (int i = 0; i < n; i++) {
            int mask = 0;
            for (char c : words[i].toCharArray()) {
                mask |= 1 << (c - 'a');
            }
            masks[i] = mask;
            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) {
                    int product = lengths[i] * lengths[j];
                    if (product > maxProduct) {
                        maxProduct = product;
                    }
                }
            }
        }

        return maxProduct;
    }
}

---

6. Dry Run Examples

Example 1

Input:

["abcw","baz","foo","bar","xtfn","abcdef"]

Masks computed.

Pair checks:

• “abcw” & “xtfn” share none
• lengths: 4 * 4 = 16
  Largest found.

Output:

16

---

Example 2

Input:

["a","ab","abc","d","cd","bcd","abcd"]

Best pair:

"ab" and "cd" → 2 * 2 = 4

Output:

4

---

Example 3

Input:

["a","aa","aaa","aaaa"]

All share letter ‘a’

Output:

0

---

Example 4

Input:

["abc","def","ghij"]

Best pair:

"abc" and "ghij" → 3 * 4 = 12

Output:

12

---

Example 5

Input:

["pqrs","mnop","xy","a","bcd"]

Best:

"mnop" (4) and "pqrs" (4)
→ 16

Output:

16

---

7. Why This Solution Works

• Bitmasking converts letter-presence check to constant time
• Pair comparison reduces to bitwise AND
• Eliminates expensive character scanning
• Guarantees correctness through exact bit representation
• Efficient for all valid input sizes

---

8. Common Mistakes

1. Comparing letters character-by-character
2. Forgetting bitmask index uses (c - 'a')
3. Using | instead of & in comparison
4. Not storing lengths separately
5. Assuming uniqueness of letters (not required)