# My C++ solution, 90 ms, O(N^2) complexity, O(N) space and some thoughts

• The basic idea is to use a bit mask bitMask[i] (a special case on unordered_set) to represent the letters in the word words[i] and then compare each possible word pair (words[i] and word[j], i != j) to see if they have any common letters (bitMask[i] & bitMask[j] !=0). If not, update res;
One trick that might help speed in some cases is to sort words in a descending order of the word size and then do early stop.
Generally speaking, it is O(N^2) time complexity.

``````class Solution {
public:
int maxProduct(vector<string>& words) {
int wSize = words.size(), res=0, i, j;
if(wSize<=1) return res;
// sort words in a descending order of word length
sort(words.begin(),words.end(), [](string &left, string &right) {return left.size()>right.size();});
//build letter bit mask for each word;
for(i=0; i<wSize; ++i)
for(j=0; j<words[i].size(); ++j) bitMask[i] |= 1<<(words[i][j]-'a');
// compare each word pair with early stop (if the remaining word pairs can not generate a larger res, then return)
for(i=0; i<wSize-1 && res < int(words[i].size())*int(words[i+1].size()) ;++i)
for(j=i+1; j<wSize; ++j)
{
res = max(res, int(words[i].size()) * int(words[j].size()));
break;
}
return res;

}
};
``````

Another thought, since we sort the words array, we may be able to take advantage of that, Say use another Bit Vector letterMask[j] kind of data structure to save all the word indices i that words[i] don't have letter 'a'+j. Then use bit and operation to find all the words that don't have all the letters in words[i]. Then use some bit operation trick (e.g. find the rightmost "1" bit) to find the one with the longest size. Following this line, I came up with the following solution, but it performs even worse, 100ms.
Not sure how to come up a better solution,

``````class Solution {
public:
int maxProduct(vector<string>& words) {
int wSize = words.size(), res=0, i, j, k, bigI;
if(wSize<=1) return res;
const int lSize = 1 + (wSize-1)/32;
unsigned int temp;

unordered_map<unsigned int, int> map;
for(i=0; i<32; ++i) map[1<<i] = i;
sort(words.begin(),words.end(), [](string &left, string &right) {return left.size()>right.size();});

for(i=0; i<wSize; ++i)
for(j=0; j<words[i].size(); ++j)
{
letMask[words[i][j]-'a'][i>>5] |= 1<<(i % 32 );
}

for(i=0; i<wSize-1 && res < int(words[i].size())*int(words[i+1].size()) ;++i)
{
for(k=0; k<lSize; ++k)
{
for(j=0, temp = 0; j<26; ++j)
{
}
temp = ~temp;
if(temp!=0)
{
bigI = k*32 + map[temp & -temp];
if(bigI<wSize)
{
res = max(res, int(words[i].size()) * int(words[bigI].size()));
break;
}
}
}
}
return res;

}
};``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.