#318

Medium

LeetCode Problem Workspace

Maximum Product of Word Lengths

The problem requires finding the maximum product of lengths of two words from an array, where the words don't share common letters.

array string bit manipulation

Problem Statement

Given a string array words, your task is to return the maximum value of length(word[i]) * length(word[j]) such that the two words word[i] and word[j] do not share any common letters. If no such pair of words exists, return 0.

The words in the array consist only of lowercase English letters, and the length of each word can vary. The goal is to efficiently determine the maximum product of the lengths of two words that have no overlapping characters.

Examples

Example 1

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

Output: 16

The two words can be "abcw", "xtfn".

Example 2

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

Output: 4

The two words can be "ab", "cd".

Example 3

Input: words = ["a","aa","aaa","aaaa"]

Output: 0

No such pair of words.

Constraints

2 <= words.length <= 1000
1 <= words[i].length <= 1000
words[i] consists only of lowercase English letters.

Solution Approach

Bitmask Representation of Words

Each word is represented as a 32-bit bitmask where each bit indicates whether a corresponding letter (from 'a' to 'z') is present in the word. This allows us to efficiently check if two words share common letters by performing a bitwise AND operation.

Compare Bitmasks for Non-Overlapping Words

For each pair of words, compare their bitmasks using a bitwise AND operation. If the result is 0, the words do not share common letters. The product of their lengths is then calculated and tracked for the maximum value.

Optimization with Precomputed Bitmasks

Precompute the bitmasks for all words before comparing pairs. This reduces redundant computations, improving performance. By using a bitmask for each word, checking if two words share letters becomes a constant-time operation.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time complexity depends on the number of words and their length. Using bit manipulation, the solution achieves an efficient comparison of word pairs. The space complexity is O(n), where n is the number of words, due to storing the bitmask for each word.

What Interviewers Usually Probe

Candidate demonstrates understanding of bitwise operations and how they can optimize comparisons.
Candidate is able to recognize the problem pattern of bit manipulation combined with array processing.
Candidate provides an efficient solution that handles up to the input constraints.

Common Pitfalls or Variants

Common pitfalls

Not using bitwise operations correctly, leading to inefficient comparisons or incorrect results.
Failing to precompute the bitmask for each word, resulting in unnecessary recomputation during the pair comparison phase.
Overlooking edge cases, such as when no valid pairs of words exist, which would require returning 0.

Follow-up variants

Increasing the size of the input array and the length of each word to test the solution's scalability.
Modifying the problem to consider uppercase letters or non-alphabetical characters and adjusting the bitmask approach accordingly.
Introducing additional constraints such as limiting the number of words that can share common letters.

FAQ

How does bit manipulation help solve the Maximum Product of Word Lengths problem?

Bit manipulation allows efficient comparison of words by representing them as bitmasks. This approach enables constant-time checks for overlapping characters, significantly speeding up the solution.

What is the time complexity of the solution?

The time complexity is O(n^2), where n is the number of words, because every pair of words must be checked. However, using bitmasks optimizes the comparison step.

Can the solution handle the upper input limits?

Yes, the solution can handle up to 1000 words, each of up to 1000 characters, by using efficient bitwise operations to minimize redundant calculations.

What is the space complexity of the solution?

The space complexity is O(n), where n is the number of words, as we store a bitmask for each word.

How can the problem be optimized further?

The problem is already optimized by using bitmasks for constant-time word comparison. Further optimizations could focus on reducing the number of word pairs to check, depending on additional constraints.

terminal

Solution

Solution 1: Bit Manipulation

The problem requires us to find two strings without common letters, so that their length product is maximized. We can represent each string with a binary number $mask[i]$, where each bit of this binary number indicates whether the string contains a certain letter. If two strings do not have common letters, then the bitwise AND result of the two binary numbers corresponding to these strings is $0$, that is, $mask[i] \& mask[j] = 0$.

1

2

3

4

5

6

7

8

9

10

11

class Solution:
    def maxProduct(self, words: List[str]) -> int:
        mask = [0] * len(words)
        ans = 0
        for i, s in enumerate(words):
            for c in s:
                mask[i] |= 1 << (ord(c) - ord("a"))
            for j, t in enumerate(words[:i]):
                if (mask[i] & mask[j]) == 0:
                    ans = max(ans, len(s) * len(t))
        return ans

Solution 2

#### Python3

1

2

3

4

5

6

7

8

9

10

11

class Solution:
    def maxProduct(self, words: List[str]) -> int:
        mask = [0] * len(words)
        ans = 0
        for i, s in enumerate(words):
            for c in s:
                mask[i] |= 1 << (ord(c) - ord("a"))
            for j, t in enumerate(words[:i]):
                if (mask[i] & mask[j]) == 0:
                    ans = max(ans, len(s) * len(t))
        return ans

Continue Practicing

#691 stickers to spell word #943 find the shortest superstring #1177 can make palindrome from substring