Problem Description

You are given an array of strings words. Your task is to find two words from this array that don't share any common letters, and maximize the product of their lengths.

For each pair of words that have no letters in common, calculate the product of their lengths. Return the maximum such product. If no two words exist without common letters, return 0.

For example:

• If words = ["abcw", "baz", "foo", "bar", "xtfn", "abcdef"]
• The words "abcw" and "xtfn" share no common letters
• Their lengths are 4 and 4, giving a product of 16
• This would be one valid product to consider

The solution uses bit manipulation to efficiently check if two words share common letters. Each word is represented as a binary number where each bit position corresponds to a letter (a-z). If bit position i is set to 1, it means the word contains the letter at position i of the alphabet.

When two words don't share any common letters, the bitwise AND of their binary representations equals 0. The algorithm:

1. Creates a binary mask for each word by setting appropriate bits for each letter present
2. For each word, checks all previously processed words
3. If two words have no common letters (their masks AND to 0), calculates the product of their lengths
4. Keeps track of the maximum product found

Intuition

The key insight is recognizing that checking if two words share common letters is fundamentally a set intersection problem. We need to determine if the set of letters in one word overlaps with the set of letters in another word.

Initially, we might think of using hash sets or iterating through each character of both words to check for common letters. However, this would be inefficient, especially when we need to compare every pair of words.

Since we're dealing with lowercase English letters (only 26 possible characters), we can use a clever optimization: represent each word's character set as a single integer using bit manipulation. Each of the 26 bits in an integer can represent whether a specific letter (a-z) is present in the word.

For example:

• The word "abc" would have bits 0, 1, and 2 set (representing 'a', 'b', 'c')
• The word "def" would have bits 3, 4, and 5 set (representing 'd', 'e', 'f')

Why is this powerful? Because checking if two words share common letters becomes a simple bitwise AND operation. If two words have no common letters, their bit representations will have no overlapping 1s, so mask1 & mask2 = 0.

This transforms our problem from a string comparison problem to a bit manipulation problem:

1. Pre-compute a bitmask for each word (O(total characters in all words))
2. Compare pairs of words using a single bitwise operation (O(1) per comparison)

The beauty of this approach is that we reduce the complexity of checking common letters from O(length1 × length2) to O(1) after the initial preprocessing, making the overall solution much more efficient.

Solution Approach

The implementation uses bit manipulation to efficiently track and compare character sets between words.

Step 1: Initialize Data Structures

• Create a mask array of the same length as words to store the bitmask representation of each word
• Initialize ans = 0 to track the maximum product

Step 2: Process Each Word For each word at index i:

1. Build the bitmask: Iterate through each character c in the current word

   • Calculate the bit position: ord(c) - ord("a") gives us a value from 0-25
   • Set the corresponding bit: mask[i] |= 1 << (ord(c) - ord("a"))
   • The |= operator ensures we set the bit without affecting other already-set bits

2. Compare with previous words: Check all words with index j < i

   • Perform bitwise AND: mask[i] & mask[j]
   • If the result equals 0, the words share no common letters
   • Update the answer: ans = max(ans, len(words[i]) * len(words[j]))

Example Walkthrough: Let's say we have words = ["abc", "def", "ab"]

• For "abc": mask[0] = 0b111 (bits 0, 1, 2 set)
• For "def": mask[1] = 0b111000 (bits 3, 4, 5 set)
  • Check with "abc": 0b111 & 0b111000 = 0 ✓ No common letters
  • Update ans = 3 * 3 = 9
• For "ab": mask[2] = 0b11 (bits 0, 1 set)
  • Check with "abc": 0b11 & 0b111 = 0b11 ≠ 0 ✗ Has common letters
  • Check with "def": 0b11 & 0b111000 = 0 ✓ No common letters
  • Update ans = max(9, 2 * 3) = 9

Time Complexity: O(n² + N) where n is the number of words and N is the total number of characters across all words Space Complexity: O(n) for storing the bitmasks

Example Walkthrough

Let's walk through a concrete example with words = ["ac", "bed", "fg"] to illustrate how the bit manipulation solution works.

Step 1: Build bitmask for "ac" (index 0)

• For 'a': position = 0, set bit 0: mask[0] = 0b1
• For 'c': position = 2, set bit 2: mask[0] = 0b101
• Final mask for "ac": 0b101 (bits 0 and 2 are set)

Step 2: Build bitmask for "bed" (index 1)

• For 'b': position = 1, set bit 1: mask[1] = 0b10
• For 'e': position = 4, set bit 4: mask[1] = 0b10010
• For 'd': position = 3, set bit 3: mask[1] = 0b11010
• Final mask for "bed": 0b11010 (bits 1, 3, and 4 are set)

Now check "bed" against all previous words:

• Compare with "ac": 0b11010 & 0b101 = 0b0 ✓ (no common letters)
• Product = length("bed") × length("ac") = 3 × 2 = 6
• Update ans = 6

Step 3: Build bitmask for "fg" (index 2)

• For 'f': position = 5, set bit 5: mask[2] = 0b100000
• For 'g': position = 6, set bit 6: mask[2] = 0b1100000
• Final mask for "fg": 0b1100000 (bits 5 and 6 are set)

Now check "fg" against all previous words:

• Compare with "ac": 0b1100000 & 0b101 = 0b0 ✓ (no common letters)
  • Product = 2 × 2 = 4 (less than current ans = 6)
• Compare with "bed": 0b1100000 & 0b11010 = 0b0 ✓ (no common letters)
  • Product = 2 × 3 = 6 (equal to current ans = 6)

Final Result: Maximum product = 6 (from "ac" and "bed")

The key insight: By representing each word as a bitmask, we can check for common letters with a single AND operation instead of comparing every character pair.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n^2 + L)

The time complexity consists of two main components:

• Building the bitmask for each word: For each word i in the array, we iterate through all its characters. This takes O(L) time total, where L is the sum of lengths of all strings.
• Comparing pairs of words: For each word i, we compare it with all previous words j < i using the bitmask AND operation. This results in O(n^2) comparisons, where n is the number of words.

Therefore, the overall time complexity is O(n^2 + L).

Space Complexity: O(n)

The space complexity is determined by:

• The mask array which stores one integer bitmask for each of the n words, requiring O(n) space.
• Other variables like ans, i, j, s, t, and c use constant space O(1).

Therefore, the overall space complexity is O(n).

Common Pitfalls

1. Duplicate Characters Within a Word

A common misconception is thinking that duplicate characters in a word need special handling or might affect the bitmask differently.

The Pitfall: Beginners might try to count character frequencies or use more complex data structures, thinking that "aaa" needs different treatment than "a".

Why It's Not a Problem: The bitwise OR operation (|=) is idempotent - setting a bit that's already set doesn't change anything. Whether a word contains 'a' once or multiple times, bit position 0 will simply be set to 1.

# Both "a" and "aaa" produce the same bitmask
word1 = "a"    # bitmask: 0b1
word2 = "aaa"  # bitmask: 0b1 (same!)

2. Incorrect Bit Position Calculation

Using the wrong formula to calculate which bit to set can lead to incorrect results or runtime errors.

The Pitfall:

# WRONG: Might cause negative bit positions or incorrect mapping
bitmasks[i] |= 1 << (ord('a') - ord(char))  # Reversed subtraction
bitmasks[i] |= 1 << ord(char)               # No normalization to 0-25

The Solution: Always use ord(char) - ord('a') to ensure:

• 'a' maps to bit 0
• 'z' maps to bit 25
• All positions are within the valid range [0, 25]

3. Checking All Pairs Instead of Previous Words Only

Some might iterate through all pairs (i, j) where i ≠ j, leading to duplicate comparisons.

The Pitfall:

# INEFFICIENT: Checks each pair twice
for i in range(len(words)):
    for j in range(len(words)):
        if i != j and (bitmasks[i] & bitmasks[j]) == 0:
            max_product = max(max_product, len(words[i]) * len(words[j]))

The Solution: Only check j < i since multiplication is commutative. Checking "abc" vs "def" gives the same product as "def" vs "abc", so we only need to check once.

4. Integer Overflow Concerns (Language-Specific)

While Python handles arbitrary-precision integers automatically, in languages like Java or C++, you might worry about bitmask overflow with 26 bits.

Why It's Not a Problem: A 32-bit integer can handle all 26 letters (we only need 26 bits), and the product of two word lengths typically fits in standard integer types for reasonable input constraints.

5. Forgetting Edge Cases

Not handling arrays with fewer than 2 words or empty strings properly.

The Solution: The provided code naturally handles these:

• If len(words) < 2: The inner loop never executes, returning 0
• Empty strings: Create a bitmask of 0, work correctly with the logic