318. Maximum Product of Word Lengths

Description

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 <= 1000
• 1 <= words[i].length <= 1000
• words[i] consists only of lowercase English letters.

Solutions

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

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.

• class Solution {
public int maxProduct(String[] words) {
int n = words.length;
int ans = 0;
for (int i = 0; i < n; ++i) {
for (char c : words[i].toCharArray()) {
mask[i] |= 1 << (c - 'a');
}
for (int j = 0; j < i; ++j) {
ans = Math.max(ans, words[i].length() * words[j].length());
}
}
}
return ans;
}
}

• class Solution {
public:
int maxProduct(vector<string>& words) {
int n = words.size();
int ans = 0;
for (int i = 0; i < n; ++i) {
for (char& c : words[i]) {
mask[i] |= 1 << (c - 'a');
}
for (int j = 0; j < i; ++j) {
ans = max(ans, (int) (words[i].size() * words[j].size()));
}
}
}
return ans;
}
};

• class Solution:
def maxProduct(self, words: List[str]) -> int:
n = len(words)
for i, word in enumerate(words):
for ch in word:
mask[i] |= 1 << (ord(ch) - ord('a'))
ans = 0
for i in range(n - 1):
for j in range(i + 1, n):
ans = max(ans, len(words[i]) * len(words[j]))
return ans

############

class Solution(object):
def maxProduct(self, words):
"""
:type words: List[str]
:rtype: int
"""
bitmap = [0] * len(words)
ans = 0
for i in range(0, len(words)):
word = words[i]
for c in word:
bitmap[i] |= (mask << (ord(c) - ord('a')))
for i in range(0, len(words)):
for j in range(0, i):
if bitmap[i] & bitmap[j] == 0:
ans = max(ans, len(words[i]) * len(words[j]))

return ans


• func maxProduct(words []string) (ans int) {
n := len(words)
for i, s := range words {
for _, c := range s {
mask[i] |= 1 << (c - 'a')
}
for j, t := range words[:i] {
ans = max(ans, len(s)*len(t))
}
}
}
return
}

• function maxProduct(words: string[]): number {
const n = words.length;
let ans = 0;
for (let i = 0; i < n; ++i) {
for (const c of words[i]) {
mask[i] |= 1 << (c.charCodeAt(0) - 'a'.charCodeAt(0));
}
for (let j = 0; j < i; ++j) {