Leetcode

Longest Uncommon Subsequence II

May 26, 2022 by aAshish

  • 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))
        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;
  }

  // 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:
        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