Skip to content

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<string>& strs) {
    unordered_set<string> seen;
    unordered_set<string> duplicates;

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

    ranges::sort(strs, ranges::greater{},
                 [](const string& s) { return s.length(); });

    for (int i = 0; i < strs.size(); ++i) {
      if (duplicates.contains(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<String> seen = new HashSet<>();
    Set<String> 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 x: -len(x))

    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