# 116ms c++ solution use early pruning (faster than most O(N^2))

• Sort the vector first according to the length of string. Then use some early pruning to fasten the process.

The worst cases would still be O(N^2). It's faster than most O(N^2) solutions. I don't know whether we can do better. (Binary Search Seems Not work here) Any comments is welcomed.

Update: We can use counting sort to improve the time complexity of sorting to O(N).

``````class Solution {
public:
int maxProduct(vector<string>& words) {
int s=words.size();
if(s==0) return 0;
vector<int> bit(s,0);
sort(words.begin(), words.end(), compare);  //sort the vector from longest to shortest
for(int i=0; i<s; i++){ //bit manipulation
for(int j=0; j<words[i].size(); j++) bit[i] |=(1<<(words[i][j]-'a'));
}
int maxlength=0;
for(int i=0; i<s-1; i++){
int si=words[i].size();
if(si*si<=maxlength) break; //early pruning
for(int j=i+1; j<s; j++){
int sj=words[j].size();
if(si*sj<=maxlength) break;  //early pruning
if((bit[i]&bit[j])==0) maxlength=si*sj;
}
}
return maxlength;
}
static bool compare(string a, string b){
return a.size()>b.size();
}
};``````

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