Maximum Product of Word Lengths

▶

Steps

setup

Initialize variables and start mask creation

We start by initializing an empty list 'masks' to store each word's bitmask and length. The first word 'abcw' is about to be processed.

💡 This step sets up the data structure to hold bitmasks, which is crucial for efficient letter overlap checks.

Line:

masks = []

💡 We need a way to represent each word's letters compactly for fast comparisons.

fill_row

Create bitmask for 'abcw' - set bit for 'a'

For the word 'abcw', we set the bit corresponding to letter 'a' (bit 31 from right, representing 'a'). The mask is updated by OR-ing with 1 shifted by (ord('a') - ord('a')) = 0.

💡 Setting bits for each letter encodes the word's letters into a single integer for quick overlap checks.

Line:

mask |= 1 << (ord(ch) - ord('a'))

💡 Bit 31 (LSB) corresponds to 'a', so setting it marks 'a' as present in the word.

fill_row

Create bitmask for 'abcw' - set bit for 'b'

Next, set the bit for letter 'b' (bit 30 from right). The mask is OR-ed with 1 shifted by 1.

💡 Each letter sets a unique bit, building the mask for the entire word.

Line:

mask |= 1 << (ord(ch) - ord('a'))

💡 Bit 30 set means 'b' is included in the word.

fill_row

Create bitmask for 'abcw' - set bit for 'c'

Set the bit for letter 'c' (bit 29 from right). The mask is OR-ed with 1 shifted by 2.

💡 Continuing to build the mask for 'abcw'.

Line:

mask |= 1 << (ord(ch) - ord('a'))

💡 Bit 29 set means 'c' is included.

fill_row

Create bitmask for 'abcw' - set bit for 'w'

Set the bit for letter 'w' (bit 9 from right). The mask is OR-ed with 1 shifted by 22.

💡 Adding the last letter 'w' to the mask.

Line:

mask |= 1 << (ord(ch) - ord('a'))

💡 Bit 9 set means 'w' is included.

fill_row

Store mask and length for 'abcw'

Append the tuple (mask, length) for 'abcw' to the masks list.

💡 Storing the mask and length allows sorting and comparisons later.

Line:

masks.append((mask, len(word)))

💡 We now have a compact representation of 'abcw' for future use.

expand

Sort masks by length descending

After all words are processed similarly, the masks list is sorted by word length in descending order.

💡 Sorting helps prune comparisons by length early.

Line:

masks.sort(key=lambda x: x[1], reverse=True)

💡 Words with longer lengths come first, enabling early breaks in nested loops.

compare

Compare masks of 'abcdef' and 'abcw' - check overlap

Compare the bitmask of 'abcdef' with 'abcw' using bitwise AND to check if they share letters.

💡 Bitwise AND zero means no common letters, allowing product calculation.

Line:

if (masks[i][0] & masks[j][0]) == 0:

💡 Shared letters prevent using this pair for max product.

compare

Compare masks of 'abcw' and 'xtfn' - check overlap

Compare bitmasks of 'abcw' and 'xtfn' with bitwise AND to check for shared letters.

💡 If no overlap, product of lengths can update max product.

Line:

if (masks[i][0] & masks[j][0]) == 0:

💡 These words can be paired for max product calculation.

insert

Update max product to 16

Since 'abcw' and 'xtfn' share no letters, update max product to 4 * 4 = 16.

💡 Updating max product tracks the best pair found so far.

Line:

max_prod = max(max_prod, masks[i][1] * masks[j][1])

💡 Max product reflects the largest product of lengths without letter overlap.

prune

Early pruning: break inner loop when product <= max product

When the product of lengths for a pair is less than or equal to current max product, break inner loop early to save time.

💡 Pruning avoids unnecessary comparisons once max product is found.

Line:

if masks[i][1] * masks[j][1] <= max_prod:
    break

💡 Pruning speeds up the algorithm by skipping smaller products.

reconstruct

Finish all comparisons and return max product

After all pairs are checked or pruned, return the maximum product found, which is 16.

💡 Returning the final answer completes the algorithm.

Line:

return max_prod

💡 The maximum product of lengths without shared letters is 16.

def maxProduct(words):
    n = len(words)  # STEP 1
    masks = []  # STEP 1
    for word in words:  # STEP 2-6
        mask = 0
        for ch in word:
            mask |= 1 << (ord(ch) - ord('a'))  # STEP 2-5
        masks.append((mask, len(word)))  # STEP 6

    masks.sort(key=lambda x: x[1], reverse=True)  # STEP 7

    max_prod = 0  # Initialize max product
    for i in range(n):  # STEP 8-11
        if masks[i][1] * masks[i][1] <= max_prod:  # STEP 11
            break
        for j in range(i + 1, n):
            if masks[i][1] * masks[j][1] <= max_prod:  # STEP 11
                break
            if (masks[i][0] & masks[j][0]) == 0:  # STEP 8,9
                max_prod = max(max_prod, masks[i][1] * masks[j][1])  # STEP 10
    return max_prod  # STEP 12

if __name__ == '__main__':
    words = ["abcw","baz","foo","bar","xtfn","abcdef"]
    print(maxProduct(words))  # Output: 16

📊

Maximum Product of Word Lengths - Watch the Algorithm Execute, Step by Step

Watching each bitmask creation and pairwise comparison visually reveals how bit manipulation efficiently solves the problem, which is hard to grasp from code alone.

Initialize masks list

A

0

0

0

0

0

0

0

0

=0

B

Set bit for 'a'

A

0

1

=1

B

💡 Bit 31 (LSB) corresponds to 'a' in this visualization (index 31 = LSB).

Set bit for 'b'

A

0

1

1

=3

B

💡 Bits 31 and 30 set represent 'a' and 'b'.

Set bit for 'c'

A

0

1

1

1

1

=7

B

💡 Bits 31,30,29 set represent 'a','b','c'.

Set bit for 'w'

A

0

0

0

0

0

0

0

0

=4194311

B

💡 Bits for 'a','b','c','w' set in mask.

Store mask and length

A

0

0

0

0

0

0

0

0

=4194311

B

💡 Mask-length tuple stored for 'abcw'.

Sort masks by length

A

0

0

0

0

0

0

0

0

=4194311

B

💡 Masks ordered by descending length.

Check overlap

A

0

1

1

=63

B

0

0

0

0

0

0

0

0

=4194311

──────

=

0

1

1

=7

💡 Non-zero result means shared letters.

Check overlap

A

0

0

0

0

0

0

0

0

=4194311

B

1

0

0

0

0

0

0

0

=270336

────────────────

=

0

0

0

0

0

0

0

0

=0

💡 Zero result means no shared letters.

Update max product

A

0

1

=16

B

💡 Max product updated to 16.

Early break inner loop

A

0

1

=16

B

💡 Pruning based on length product.

Return max product

A

0

1

=16

B

💡 Final answer is 16.

Key Takeaways

✓ Bitmasking efficiently encodes word letters enabling O(1) overlap checks.

Without visualization, it's hard to see how bit operations replace nested loops over letters.

✓ Sorting words by length allows early pruning of pairs that cannot improve max product.

This optimization is subtle in code but clear when seeing the break conditions triggered visually.

✓ Bitwise AND result zero means no shared letters, a key condition for updating max product.

Visualizing the AND operation's result bits clarifies why some pairs are valid and others are not.

Practice

1. Given the following code and input, what is the final returned list?

easy

A. [2, 5]

B. [5, 4]

C. [4, 5]

D. [2, 4]

Solution

1. Step 1: Compute xor of all elements

   xor = 2 ^ 4 ^ 2 ^ 5 = (2 ^ 2) ^ 4 ^ 5 = 0 ^ 4 ^ 5 = 1 (binary 0001)

2. Step 2: Find rightmost set bit and partition

   set_bit = xor & (-xor) = 1 & (-1) = 1. Partition nums by bit 1: group1 (bit set): 5, group2 (bit not set): 2,4,2. XOR group1 = 5, XOR group2 = 4.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Output matches unique elements [OK]

Hint: Rightmost set bit partitions unique numbers correctly [OK]

Common Mistakes:

• Mixing order of output
• Incorrect xor calculation
• Miscomputing set bit

2. What is the time complexity of the brute force bit counting approach that checks each bit of a 32-bit integer one by one?

medium

A. O(log n) where n is the integer's value

B. O(n) where n is the integer's value

C. O(1) because the number of bits is fixed (32 bits)

D. O(32 * log n) due to bit shifts and counting

Solution

1. Step 1: Identify input size

   The input is an integer n, and the brute force method checks each bit by shifting until n becomes zero.

2. Step 2: Analyze loop iterations

   The number of iterations depends on the number of bits in n, which is proportional to log n.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Loop runs approximately log n times, so complexity is O(log n) [OK]

Hint: Number of bits in n is proportional to log n [OK]

Common Mistakes:

• Assuming fixed bit width means O(1)
• Confusing value magnitude with fixed bit size

3. Consider the following buggy code for generating subsets. Which line contains the subtle bug that causes all subsets in res to be the same list instance?

medium

A. Line 4: def backtrack(start, path):

B. Line 7: path.append(nums[i])

C. Line 5: res.append(path)

D. Line 9: path.pop()

Solution

1. Step 1: Identify how subsets are added to results

   Appending path directly adds a reference, not a copy, so all entries point to the same list object.

2. Step 2: Fix by appending a copy of path

   Using path[:] or list(path) creates a snapshot copy, preserving each subset uniquely.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Appending reference causes all subsets to be identical [OK]

Hint: Always append a copy of the current path [OK]

Common Mistakes:

• Appending mutable list reference instead of a copy

4. 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

5. Suppose you need to reverse bits of a 64-bit unsigned integer instead of 32-bit. Which modification to the optimal divide and conquer mask approach is correct?

hard

A. Extend masks to 64-bit constants and add an additional step shifting by 32 bits with proper masking.

B. Apply the 32-bit mask approach directly without changes; it works for any bit width.

C. Use the brute force bit-by-bit reversal loop since masks only work for 32 bits.

D. Use the same 32-bit masks and steps, but apply them twice to the lower and upper 32 bits separately.

Solution

1. Step 1: Understand mask size dependency

   The masks and shifts are designed for 32-bit integers and must be extended for 64-bit integers.

2. Step 2: Modify masks and add step

   Use 64-bit masks and add a final step shifting by 32 bits with masking to handle full 64-bit reversal.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   64-bit reversal requires 64-bit masks and an extra step [OK]

Hint: 64-bit reversal needs 64-bit masks and extra shift step [OK]

Common Mistakes:

• Trying to reuse 32-bit masks directly
• Splitting 64-bit into two 32-bit halves without merging
• Assuming brute force is only option for 64-bit