Dare2Solve
The task is to find the maximum product of the lengths of two words in a given list, such that the two words do not share any common letters. Each word contains only lowercase English letters.
To efficiently solve the problem, we can represent each word using a bitmask where each bit indicates whether a particular letter ('a' to 'z') is present in the word. This representation allows for fast comparison of whether two words have any common letters by using bitwise operations. By comparing the bitmasks of two words, we can quickly determine if they share common letters without manually checking each character.
Bitmask Representation:
000...0111
).Sorting:
Two-Word Comparison:
Optimization:
class Solution {
public:
int maxProduct(vector<string>& words) {
sort(words.begin(), words.end(), [](const string& a, const string& b) {
return b.length() < a.length();
});
int best = 0;
vector<int> bitsets(words.size(), 0);
for (int i = 0; i < words.size(); i++) {
int bitset = 0;
int wlen = words[i].length();
if (wlen * words[0].length() < best)
return best;
for (char c : words[i]) {
bitset |= (1 << (c - 'a'));
}
for (int j = 0; j < i; j++) {
if ((bitsets[j] & bitset) == 0) {
best = max(best, wlen * int(words[j].length()));
}
}
bitsets[i] = bitset;
}
return best;
}
};
class Solution:
def maxProduct(self, words: list[str]) -> int:
words.sort(key=lambda x: len(x), reverse=True)
best = 0
bitsets = [0] * len(words)
for i in range(len(words)):
bitset = 0
wlen = len(words[i])
if wlen * len(words[0]) < best:
return best
for char in words[i]:
bitset |= (1 << (ord(char) - ord('a')))
for j in range(i):
if (bitsets[j] & bitset) == 0:
best = max(best, wlen * len(words[j]))
bitsets[i] = bitset
return best
class Solution {
public int maxProduct(String[] words) {
Arrays.sort(words, (a, b) -> b.length() - a.length());
int best = 0;
int[] bitsets = new int[words.length];
for (int i = 0; i < words.length; i++) {
int bitset = 0;
int wlen = words[i].length();
if (wlen * words[0].length() < best)
return best;
for (char c : words[i].toCharArray()) {
bitset |= (1 << (c - 'a'));
}
for (int j = 0; j < i; j++) {
if ((bitsets[j] & bitset) == 0) {
best = Math.max(best, wlen * words[j].length());
}
}
bitsets[i] = bitset;
}
return best;
}
}
/**
* @param {string[]} words
* @return {number}
*/
var maxProduct = function (words) {
words.sort((a, b) => b.length - a.length)
let best = 0, bitsets = new Uint32Array(words.length)
for (let i = 0; i < words.length; i++) {
let word = words[i], wlen = word.length, bitset = 0
if (wlen * words[0].length < best)
return best
for (let j = 0; j < wlen; j++)
bitset |= 1 << (word.charCodeAt(j) - 97)
for (let j = 0; j < i; j++)
if ((bitsets[j] & bitset) === 0)
best = Math.max(best, wlen * words[j].length)
bitsets[i] = bitset
}
return best
};