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 need to count how many bits are set to 1 in a 32-bit unsigned integer. Which approach guarantees the most efficient and reliable solution regardless of input size?

easy

A. Use a greedy algorithm that counts bits by repeatedly subtracting powers of two.

B. Use built-in bit count functions provided by the language or hardware instructions.

C. Use dynamic programming to store counts of smaller bit segments and combine them.

D. Use a brute force loop checking each bit one by one with bitwise operations.

Solution

1. Step 1: Understand problem constraints

   The problem requires counting set bits in a fixed-size integer, which can be done in constant time using hardware or built-in functions.

2. Step 2: Compare approaches

   Brute force and DP approaches work but are slower (O(1) but with more operations). Greedy subtraction is inefficient and incorrect for bit counting. Built-in functions leverage optimized CPU instructions for O(1) time.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Built-in bit count functions are optimal and reliable [OK]

Hint: Built-in bit count functions use CPU instructions [OK]

Common Mistakes:

• Confusing greedy subtraction with bit counting
• Thinking DP is needed for fixed-size integers

2. The following code attempts to count set bits for all numbers from 0 to n using Brian Kernighan's trick. Identify the line containing the subtle bug that causes incorrect results.

def countBits(n):
    res = []
    for i in range(1, n + 1):
        count = 0
        x = i
        while x:
            x &= x - 1
            count += 1
        res.append(count)
    return res

medium

A. Line 3: for i in range(1, n + 1):

B. Line 2: res = []

C. Line 5: while x:

D. Line 7: res.append(count)

Solution

1. Step 1: Check loop range correctness

   The loop starts from 1, missing 0, so the count for 0 is never computed or appended.

2. Step 2: Consequence of missing 0

   Result array length is n instead of n+1, causing mismatch and incorrect output for input including 0.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Including 0 is required to match problem specification [OK]

Hint: Loop must start at 0 to include zero count [OK]

Common Mistakes:

• Starting loop at 1 instead of 0
• Appending before counting
• Incorrect while condition

3. The following code attempts to find the missing number using XOR. Which line contains the subtle bug that causes incorrect results when the missing number is n?

medium

A. Line 3: initializing xor_all to 0

B. Line 7: returning xor_all without modification

C. Line 4: iterating only to n-1 instead of n

D. Line 6: XORing array elements

Solution

1. Step 1: Analyze the loop range for XORing indices

   The loop runs from 0 to n-1 (range(n)), missing the number n itself.

2. Step 2: Understand impact on missing number detection

   Since n is not XORed, if n is the missing number, it won't be accounted for, causing wrong output.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Changing loop to range(n+1) fixes the bug [OK]

Hint: Loop must include n to XOR all indices correctly [OK]

Common Mistakes:

• Off-by-one in loop range
• Forgetting to XOR n
• Assuming initialization causes bug

4. Consider the following buggy Python code intended to generate Gray code sequence. Which line contains the subtle bug that breaks the Gray code property?

medium

A. Line 2: Using XOR with (i << 1) instead of (i >> 1)

B. Line 3: Incorrect range boundary in range(1 << n)

C. Line 1: Missing base case for n=0

D. Line 5: Printing the result instead of returning

Solution

1. Step 1: Identify the bitwise operation used

   The code uses i ^ (i << 1) instead of the correct i ^ (i >> 1).

2. Step 2: Understand impact on Gray code property

   Left shifting i doubles the value, causing incorrect bit patterns and breaking the one-bit difference property between consecutive numbers.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Correct Gray code uses right shift, not left shift [OK]

Hint: XOR with right shift generates Gray code; left shift breaks it [OK]

Common Mistakes:

• Confusing left and right bit shifts in XOR formula
• Ignoring base case n=0 which is trivial but not critical here
• Misunderstanding range boundaries or print vs return

5. If the input array can contain negative numbers and the bit counting approach is used, what modification is necessary to correctly find the single number?

hard

A. Use a 32-bit mask and handle sign bit separately to avoid sign extension errors.

B. Use a hash map instead, as bit counting cannot handle negatives.

C. Convert all numbers to positive before bit counting and restore sign later.

D. No modification needed; bit counting works the same for negatives.

Solution

1. Step 1: Understand bit counting with negative numbers

   Negative numbers use two's complement; sign bit must be handled carefully to avoid incorrect counts.

2. Step 2: Apply 32-bit mask and handle sign bit

   Counting bits with a mask ensures correct accumulation; sign bit handled separately prevents sign extension issues.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Proper masking ensures correct bit counts for negatives [OK]

Hint: Mask bits to handle sign bit correctly in negative numbers [OK]

Common Mistakes:

• Ignoring sign bit causes wrong results
• Assuming negatives behave like positives