# Clean C++ O(n^2) with Explanation

• Very naive solution. Find the max Len of a string that is has no common subsequence of any other string.

``````class Solution {
public:
//This is used to determine if a has common subsequence in b
bool hasCommon(string a,string b){
int remine = a.size();
int remine2 = b.size();
for(;remine>0&&remine2>0;){
int i = a.size()-remine;
int j = b.size()-remine2;
if(a.at(i) == b.at(j)){
remine--;remine2--;
}else{
remine2--;
}
}
return remine==0;
}
int findLUSlength(vector<string>& strs) {
int maxLen = -1;
for(int i = 0;i<strs.size();++i){
int currentLen = strs[i].length();
bool all = true;
for(int j = 0;j<strs.size();++j){
if(i!=j&&hasCommon(strs[i], strs[j])){
all = false;
break;
}
}
if(all){
maxLen = maxLen<currentLen?currentLen:maxLen;
}
}
return maxLen;
}
};
``````

• Hi I think this solution is based on a presumption that the longest uncommon subsequence always should be a whole string in the vector. Is that true? How to prove it?

• If a uncommon subsequence `subseq` is the subsequence of a string `str`, this means that `subseq` isn't contained in any other string. hence, the complet string `str` which is more "complicated" should neither be contained in any other string.

• Doesn't look like O(n^2). But what do you mean with n?

• This solution looks like it is O(n^2 * avg_length^2), where n is of num of strings and avg_length is the average length of all strings

• @pinkfloyda Yes, you're right.

• Doesn't look like O(n^2). But what do you mean with n?

Yep, @pinkfloyda has nicely gaven the correction. Thanks. I haven't thought about the complexity of hasCommon

• @pinkfloyda Should it be O(n^2*avg_length)? Assuming comparison O(avg_length).

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