Given a string array words, return the maximum value of length(word[i]) * length(word[j]) where the two words do not share common letters. If no such two words exist, return 0.
Example 1:
Input: words = ["abcw","baz","foo","bar","xtfn","abcdef"] Output: 16 Explanation: The two words can be "abcw", "xtfn".
Example 2:
Input: words = ["a","ab","abc","d","cd","bcd","abcd"] Output: 4 Explanation: The two words can be "ab", "cd".
Example 3:
Input: words = ["a","aa","aaa","aaaa"] Output: 0 Explanation: No such pair of words.
Constraints:
2 <= words.length <= 10001 <= words[i].length <= 1000words[i] consists only of lowercase English letters.Problem Overview: You receive an array of lowercase words. The task is to choose two words that share no common characters and maximize the product of their lengths. If every pair shares at least one character, the result is 0.
Approach 1: Nested Loop with Set Comparison (Time: O(n^2 * L), Space: O(L))
The straightforward strategy compares every pair of words. For each word, build a set of characters, then iterate through all pairs using a nested loop. For each pair, check if the two sets intersect. If they share no characters, compute len(word1) * len(word2) and update the maximum product.
This method works because set membership and intersection checks are fast in practice, but the algorithm still evaluates all n^2 pairs. Each comparison may scan up to L characters depending on the implementation. This approach is easy to implement and good for understanding the core constraint: verifying that two strings share no characters.
Approach 2: Bitmask for Character Representation (Time: O(n^2), Space: O(n))
The optimized approach converts each word into a 26‑bit integer mask. Each bit represents whether a character from 'a' to 'z' appears in the word. For example, if a word contains a and c, the mask will have bits 0 and 2 set.
Once every word has a bitmask, compare pairs using a single bitwise operation. If mask[i] & mask[j] == 0, the words share no characters. Compute the product of their lengths and track the maximum. The key insight: bitwise AND instantly detects shared characters without scanning strings.
Mask creation takes O(n * L), and pair comparisons take O(n^2). Each check is constant time due to bit manipulation. This dramatically reduces overhead compared with repeated set checks. The input itself is stored in an array, and only one mask per word is required.
Recommended for interviews: Start by explaining the nested loop approach to demonstrate understanding of the constraint. Then transition to the bitmask optimization. Interviewers typically expect the bitmask solution because it converts character comparisons into constant‑time bit operations while keeping the overall complexity at O(n^2).
This approach uses bit manipulation to represent each word with a bitmask where each bit corresponds to a character ('a' to 'z'). This allows comparison of character sets in constant time using a bitwise AND operation. If two words have no common characters, their corresponding bitmask AND result should be zero.
The solution first computes a bitmask for each word using each character's position in the alphabet. Then, it iterates through all possible pairs of words, checking if their bitmasks overlap. If they do not overlap, it means the words do not share common letters, and it calculates their length product, updating the maximum product accordingly.
Time Complexity: O(N^2 + L), where N is the number of words and L is the total number of characters across all words.
Space Complexity: O(N), as we require an array to store bit masks for each word.
This approach involves iterating through each pair of words, using a set to represent the characters of each word. For each pair, it checks if there are any common letters using set intersection. This method is straightforward but less efficient than bit manipulation for larger input sizes.
In this Python solution, each word is converted into a set of characters. The method then goes through each pair of words and checks for common letters using set intersection. If no common letters exist—and thereby the intersection is an empty set—it calculates their length product and updates the maximum product.
Time Complexity: O(N^2 * L) where L is the average length of the words.
Space Complexity: O(N * L) as each word is stored in a set.
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.
We traverse each string. For the current string words[i] we are traversing, we first calculate the corresponding binary number mask[i], and then traverse all strings words[j] where j \in [0, i). We check whether mask[i] \& mask[j] = 0 holds. If it holds, we update the answer to max(ans, |words[i]| times |words[j]|).
After the traversal, we return the answer.
The time complexity is O(n^2 + L), and the space complexity is O(n). Here, n is the length of the string array words, and L is the sum of the lengths of all strings in the string array.
Python
Java
C++
Go
TypeScript
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Bitmask for Character Representation | Time Complexity: O(N^2 + L), where N is the number of words and L is the total number of characters across all words. |
| Nested Loop with Set Comparison | Time Complexity: O(N^2 * L) where L is the average length of the words. |
| Bit Manipulation | — |
| Default Approach | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Nested Loop with Set Comparison | O(n^2 * L) | O(L) | Simple baseline solution when optimizing character comparison is not required |
| Bitmask for Character Representation | O(n^2) | O(n) | Best general solution; converts character checks into constant-time bit operations |
Maximum Product of Word Lengths | Leetcode 318 | Live coding session | Bits Manipulation • Coding Decoded • 5,541 views views
Watch 9 more video solutions →Practice Maximum Product of Word Lengths with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor