Maximum Product of Word Lengths

📋

Problem

Imagine you have a list of words and want to find two that don't share any letters, maximizing the product of their lengths - like pairing two puzzle pieces that fit perfectly without overlap.

Given an array of strings words, find the maximum value of length(word[i]) * length(word[j]) where the two words do not share any common letters. Return 0 if no such pair exists.

1 ≤ words.length ≤ 10^51 ≤ words[i].length ≤ 1000words[i] consists only of lowercase English letters

Edge cases: All words share at least one common letter → output 0Only one word in the list → output 0Words with repeated letters but no overlap with others → product based on length

</>

IDE

def maxProduct(words: list[str]) -> int:public int maxProduct(String[] words)int maxProduct(vector<string> &words)function maxProduct(words)

def maxProduct(words):
    # Write your solution here
    pass

class Solution {
    public int maxProduct(String[] words) {
        // Write your solution here
        return 0;
    }
}

#include <vector>
using namespace std;

int maxProduct(vector<string> &words) {
    // Write your solution here
    return 0;
}

function maxProduct(words) {
    // Write your solution here
}

Common Bugs to Avoid

Wrong: 0Incorrectly assumes no pairs exist when they do; fails to check all pairs or bitmask overlap.✅ Ensure to check all pairs and use bitmask AND == 0 to detect no common letters.

Wrong: 16Returns max length sum instead of product of lengths.✅ Multiply lengths of two words, not sum, when no common letters.

Wrong: 9Fails to handle repeated letters correctly, counting duplicates as overlapping.✅ Use bitmask to represent unique letters only, ignoring duplicates.

Wrong: 20Greedy approach picks longest words without checking overlap, missing max product pair.✅ Check all pairs with bitmask AND == 0, not just longest words.

Wrong: TLEUses brute force O(n^2 * k) approach on large input.✅ Implement bitmasking and pruning to reduce complexity to O(n^2) with fast bit operations.

✓

Test Cases

Focus on handling empty and minimal inputs correctly before moving on.

Avoid greedy traps and ensure correct pairwise bitmask checks.

Optimize your solution to handle large inputs efficiently using bitmasking.

t1_01basic

Input{"words":["abcw","baz","foo","bar","xtfn","abcdef"]}

Expected16

⏱ Performance - must finish in 2000ms

The two words "abcw" and "xtfn" do not share common letters and their lengths multiply to 4 * 4 = 16, which is the maximum.

💡 Try representing each word as a bitmask of characters to quickly check overlaps.

💡 Use bitwise AND to check if two words share common letters efficiently.

💡 Calculate max product by comparing all pairs with no common bits set.

Why it failed: Incorrect output means bitmask or overlap check is wrong; fix by ensuring bitwise AND between word masks is zero before multiplying lengths.

✓ Correctly identifies max product using bitmask overlap checks.

t1_02basic

Input{"words":["a","ab","abc","d","cd","bcd","abcd"]}

Expected4

⏱ Performance - must finish in 2000ms

Words "a" and "d" have no common letters; product is 1 * 4 = 4, which is maximum.

💡 Check pairs with no common letters using bitmask AND == 0.

💡 Remember to consider single-letter words and longer words carefully.

💡 Max product comes from "a" (length 1) and "d" (length 4) with no overlap.

Why it failed: Wrong output likely from missing pairs with single-letter words; fix by including all pairs and checking bitmask overlap correctly.

✓ Correctly handles pairs including single-letter words.

t2_01edge

Input{"words":[]}

Expected0

⏱ Performance - must finish in 2000ms

Empty input array means no pairs exist, so output is 0.

💡 Consider what happens when the input list is empty.

💡 No words means no pairs, so max product must be zero.

💡 Return 0 immediately if words list is empty.

Why it failed: Code crashes or returns non-zero on empty input; fix by adding a check for empty list and returning 0.

✓ Handles empty input gracefully by returning 0.

t2_02edge

Input{"words":["abc"]}

Expected0

⏱ Performance - must finish in 2000ms

Only one word means no pair exists, so output is 0.

💡 Check behavior when only one word is present.

💡 No pairs possible with single word, so max product is zero.

💡 Return 0 if words length is less than 2.

Why it failed: Returns non-zero when only one word present; fix by returning 0 if words length < 2.

✓ Correctly returns 0 for single word input.

t2_03edge

Input{"words":["aaa","bbb","ccc"]}

Expected9

⏱ Performance - must finish in 2000ms

All words have repeated letters but no overlap; max product is 3 * 3 = 9.

💡 Repeated letters in a word don't affect bitmask representation.

💡 Check that bitmask correctly represents unique letters only.

💡 Max product is between any two words with no common letters, here 3*3=9.

Why it failed: Fails to handle repeated letters correctly; fix by using sets or bitmask to represent unique letters only.

✓ Handles repeated letters correctly by using unique letter bitmask.

t3_01corner

Input{"words":["abc","def","ghij","klmno","pqr","stuv","wxyz"]}

Expected20

⏱ Performance - must finish in 2000ms

Words "klmno" (length 5) and "wxyz" (length 4) share no letters; product 5*4=20 is max.

💡 Greedy approach picking longest words first may fail if they share letters.

💡 Check all pairs with bitmask AND == 0, not just longest words.

💡 Max product is from "klmno" and "wxyz", not longest words "ghij" and "klmno".

Why it failed: Greedy approach picking longest words first fails; fix by checking all pairs for no common letters using bitmask AND.

✓ Correctly finds max product by checking all pairs, avoiding greedy trap.

t3_02corner

Input{"words":["a","aa","aaa","aaaa","aaaaa","aaaaaa"]}

Expected0

⏱ Performance - must finish in 2000ms

All words share letter 'a', so no pair without common letters; output 0.

💡 Repeated letters in words do not create new unique letters.

💡 Bitmask AND will never be zero if all words share 'a'.

💡 Return 0 if no pair has bitmask AND == 0.

Why it failed: Fails to detect common letter overlap; fix by using bitmask AND to check no common letters.

✓ Correctly returns 0 when all words share a letter.

t3_03corner

Input{"words":["abc","def","abc","def"]}

Expected9

⏱ Performance - must finish in 2000ms

Pairs "abc" and "def" have no common letters; product 3*3=9 is max.

💡 Avoid confusion between 0/1 knapsack and this problem's pair checking.

💡 Duplicates do not affect bitmask logic; treat each word independently.

💡 Check all pairs for no common letters using bitmask AND.

Why it failed: Confuses problem with knapsack; fix by focusing on pairwise bitmask AND checks, not counting duplicates differently.

✓ Correctly handles duplicates and finds max product.

t4_01performance

Input{"_description":"n=100000 at constraint boundary - executor generates this input"}

Expectednull

⏱ Performance - must finish in 2000ms

Input size n=100000 with average word length up to 1000; O(n^2) brute force will time out, efficient bitmasking needed.

💡 Brute force O(n^2 * k) is too slow for large n.

💡 Use bitmasking to represent words and prune pairs early.

💡 Optimize with sorting and early break conditions to avoid TLE.

Why it failed: TLE due to O(n^2) brute force; fix by using bitmasking and pruning to reduce complexity.

✓ Efficient bitmasking and pruning confirmed by passing performance test.

Practice

1. You are given an array containing n distinct numbers taken from the range 0 to n. Exactly one number in this range is missing from the array. Which approach guarantees finding the missing number in O(n) time and O(1) space without sorting or summation overflow risks?

easy

A. Sorting the array and scanning for the first index where the value doesn't match the index

B. Using XOR of all indices and array elements to cancel out pairs and find the missing number

C. Using a dynamic programming approach to track missing elements

D. Using a greedy approach to pick the smallest missing number at each step

Solution

1. Step 1: Understand the problem constraints

   The array contains numbers from 0 to n with exactly one missing. The goal is to find the missing number efficiently.

2. Step 2: Identify the approach that guarantees O(n) time and O(1) space without overflow

   XOR approach works by XORing all indices and all array elements. Since XOR of a number with itself is zero, all pairs cancel out, leaving the missing number.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   XOR approach avoids sorting overhead and sum overflow [OK]

Hint: XOR cancels pairs to find missing number efficiently [OK]

Common Mistakes:

• Assuming sorting is always optimal
• Using sum approach without overflow check
• Confusing greedy with XOR logic

2. You are given an array of integers and need to find two numbers whose XOR is the maximum possible. Which approach guarantees an optimal solution for this problem?

easy

A. Build a binary trie of all numbers and traverse it to find the maximum XOR pair.

B. Use a dynamic programming approach to build XOR values incrementally.

C. Use a greedy approach by iteratively guessing the maximum XOR bit from the most significant bit down.

D. Use brute force nested loops to check XOR of every pair and track the maximum.

Solution

1. Step 1: Understand problem constraints

   We want to find two numbers maximizing XOR, which requires bitwise comparisons across all numbers.

2. Step 2: Evaluate approaches

   Brute force works but is O(n²), greedy bit-by-bit can fail on some inputs due to incomplete prefix checks, while trie-based stores bits for all numbers and efficiently finds complementary bits to maximize XOR.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Trie-based approach is optimal and guaranteed to find max XOR [OK]

Hint: Trie stores bits for efficient max XOR search [OK]

Common Mistakes:

• Believing greedy bit-by-bit always works
• Thinking DP applies here
• Assuming brute force is optimal

3. You are given an array where every element appears exactly three times except for one element which appears only once. Which approach guarantees an optimal solution with O(n) time and O(1) space complexity?

easy

A. Use a hash map to count occurrences of each element and return the one with count 1.

B. Use bitwise operations to track bits appearing once and twice, resetting bits appearing thrice.

C. Sort the array and scan to find the unique element by checking neighbors.

D. Use a dynamic programming approach to track counts of elements modulo 3.

Solution

1. Step 1: Understand the problem constraints

   The problem requires identifying the unique element appearing once while others appear thrice, with optimal time and constant space.

2. Step 2: Evaluate approaches

   Hash map uses extra space, sorting is O(n log n), DP is not straightforward here. Bitwise FSM approach tracks bits efficiently in O(n) time and O(1) space.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Bitwise FSM approach is known optimal for this problem [OK]

Hint: Bitwise FSM tracks counts mod 3 in constant space [OK]

Common Mistakes:

• Thinking sorting or hash map is optimal for space
• Confusing DP applicability here

4. What is the time complexity of the bit manipulation approach using n & (n - 1) to check if a number is a power of two, assuming n is a 32-bit integer?

medium

A. O(n), where n is the input number

B. O(n log n), due to repeated bit operations

C. O(1), constant time since integer size is fixed

D. O(log n), proportional to the number of bits in n

Solution

1. Step 1: Identify the operation cost

   The operation n & (n - 1) runs in constant time on fixed-width integers, such as 32-bit integers.

2. Step 2: Consider input size in bits

   Since the integer size is fixed (32 bits), the operation is O(1) constant time.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Bitwise operations on fixed-width integers are constant time [OK]

Hint: Bit ops on fixed-width integers are O(1) [OK]

Common Mistakes:

• Assuming O(log n) for fixed-width integers
• Confusing numeric value with bit length

5. Suppose you want to generate a Gray code sequence where each number can be repeated multiple times (i.e., reuse allowed). Which modification to the optimal bitwise formula approach correctly handles this variant?

hard

A. Use brute force backtracking to generate sequences with repeated numbers allowed.

B. Modify the formula to i ^ (i >> 1) but allow duplicates by not enforcing uniqueness in the output list.

C. Use the same XOR formula but generate only n numbers instead of 2^n.

D. No modification needed; the original formula already allows repeated numbers.

Solution

1. Step 1: Understand the reuse constraint

   Allowing repeated numbers breaks the Gray code uniqueness property, so the original formula which generates unique numbers won't work.

2. Step 2: Identify suitable approach

   Brute force backtracking can explore sequences with repeated numbers and enforce the one-bit difference condition without uniqueness constraints.

3. Step 3: Why other options fail

   Original formula always generates unique numbers; simply allowing duplicates in output breaks Gray code definition; generating fewer numbers misses full coverage.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Backtracking is flexible enough to handle reuse constraints [OK]

Hint: Original formula assumes unique numbers; reuse needs backtracking [OK]

Common Mistakes:

• Assuming original formula can be tweaked trivially for reuse
• Thinking fewer numbers still form valid Gray code
• Ignoring uniqueness property of Gray code