## Longest Uncommon Subsequence II

• Time:O(n^2\ell), where n = |\texttt{strs}| and \ell = \max(|\texttt{strs[i]}|)
• Space:O(\Sigma |\texttt{strs[i]}|)

## C++

class Solution {
public:
int findLUSlength(vector<string>& strs) {
unordered_set<string> seen;
unordered_set<string> duplicates;

for (const string& str : strs)
if (seen.count(str))
duplicates.insert(str);
else
seen.insert(str);

sort(begin(strs), end(strs),
[](const auto& a, const auto& b) { return a.length() > b.length(); });

for (int i = 0; i < strs.size(); ++i) {
if (duplicates.count(strs[i]))
continue;
bool isASubsequence = false;
for (int j = 0; j < i; ++j)
isASubsequence |= isSubsequence(strs[i], strs[j]);
if (!isASubsequence)
return strs[i].length();
}

return -1;
}

private:
// return true if a is a subsequence of b
bool isSubsequence(const string& a, const string& b) {
int i = 0;
for (const char c : b)
if (i < a.length() && c == a[i])
++i;
return i == a.length();
};
};


## JAVA

class Solution {
public int findLUSlength(String[] strs) {
Set<String> seen = new HashSet<>();
Set<String> duplicates = new HashSet<>();

for (final String str : strs)
if (seen.contains(str))
else

Arrays.sort(strs, (a, b) -> b.length() - a.length());

for (int i = 0; i < strs.length; ++i) {
if (duplicates.contains(strs[i]))
continue;
boolean isASubsequence = false;
for (int j = 0; j < i; ++j)
isASubsequence |= isSubsequence(strs[i], strs[j]);
if (!isASubsequence)
return strs[i].length();
}

return -1;
}

// return true if a is a subsequence of b
private boolean isSubsequence(final String a, final String b) {
int i = 0;
for (final char c : b.toCharArray())
if (i < a.length() && c == a.charAt(i))
++i;
return i == a.length();
}
}


## Python

class Solution:
def findLUSlength(self, strs: List[str]) -> int:
def isSubsequence(a: str, b: str) -> bool:
i = 0
j = 0

while i < len(a) and j < len(b):
if a[i] == b[j]:
i += 1
j += 1

return i == len(a)

seen = set()
duplicates = set()

for s in strs:
if s in seen:

strs.sort(key=lambda s: -len(s))

for i in range(len(strs)):
if strs[i] in duplicates:
continue
isASubsequence = False
for j in range(i):
isASubsequence |= isSubsequence(strs[i], strs[j])
if not isASubsequence:
return len(strs[i])

return -1