Maximum Product of Word Lengths
Medium · Bit Manipulation · Explanation and code example
Letter Masks and Pair Comparison
How it works
Represent the letters of each word with a 26-bit mask. Repeated occurrences do not change the mask. Two words have no common letter exactly when their masks have zero bitwise intersection; compare the products of lengths for these pairs.
Steps
- Build one letter mask per word.
- Check each pair with mask[i] & mask[j].
- Update the maximum length product when the masks are disjoint.
Complexity
- Time: O(L + w²), for total characters L and w words.
- Space: O(w).
Things to watch for
- Use bitwise OR while building masks.
- Repeated letters do not occupy new bits.
- The product uses original word lengths, rather than distinct-letter counts.
Python code example
class Solution:
def maxProduct(self, words: list[str]) -> int:
ans = 0
def getMask(word: str) -> int:
mask = 0
for c in word:
mask |= 1 << ord(c) - ord('a')
return mask
masks = [getMask(word) for word in words]
for i in range(len(words)):
for j in range(i):
if not (masks[i] & masks[j]):
ans = max(ans, len(words[i]) * len(words[j]))
return ans
C++ code example
class Solution {
public:
int maxProduct(vector<string>& words) {
size_t ans = 0;
vector<int> masks;
for (const string& word : words)
masks.push_back(getMask(word));
for (int i = 0; i < words.size(); ++i)
for (int j = 0; j < i; ++j)
if ((masks[i] & masks[j]) == 0)
ans = max(ans, words[i].length() * words[j].length());
return ans;
}
private:
int getMask(const string& word) {
int mask = 0;
for (const char c : word)
mask |= 1 << c - 'a';
return mask;
}
};
Source and license
Explanation by LC Tracker. Code adapted from walkccc / Peng-Yu Chen · MIT license. Node types are supplied by LeetCode where needed.