522. 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]}|)$
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 class Solution { public: int findLUSlength(vector& strs) { unordered_set seen; unordered_set 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: // Returns 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(); }; }; 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 class Solution { public int findLUSlength(String[] strs) { Set seen = new HashSet<>(); Set duplicates = new HashSet<>(); for (final String str : strs) if (seen.contains(str)) duplicates.add(str); else seen.add(str); 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; } // Returns 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(); } } 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 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: duplicates.add(s) seen.add(s) 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