522. Longest Uncommon Subsequence II

Problem Link

Description

---

Given an array of strings strs, return the length of the longest uncommon subsequence between them. If the longest uncommon subsequence does not exist, return -1.

An uncommon subsequence between an array of strings is a string that is a subsequence of one string but not the others.

A subsequence of a string s is a string that can be obtained after deleting any number of characters from s.

• For example, "abc" is a subsequence of "aebdc" because you can delete the underlined characters in "aebdc" to get "abc". Other subsequences of "aebdc" include "aebdc", "aeb", and "" (empty string).

 

Example 1:

Input: strs = ["aba","cdc","eae"]
Output: 3

Example 2:

Input: strs = ["aaa","aaa","aa"]
Output: -1

 

Constraints:

• 2 <= strs.length <= 50
• 1 <= strs[i].length <= 10
• strs[i] consists of lowercase English letters.

Solution

---

Python3

class Solution:
    def findLUSlength(self, words: List[str]) -> int:
        
        def getDuplicates():
            sset = set()
            duplicates = set()
            
            for word in words:
                if word in sset:
                    duplicates.add(word)
                sset.add(word)
            
            return duplicates
        
        def isSubsequence(a, b):
            i = j = 0
            
            while i < len(a) and j < len(b):
                if a[i] == b[j]: j += 1
                i += 1
            
            return j == len(b)
        
        words.sort(key = len, reverse = 1)
        duplicates = getDuplicates()
        if words[0] not in duplicates: return len(words[0])
        
        for i, word in enumerate(words):
            if word not in duplicates:
                for j in range(i):
                    if isSubsequence(words[j], words[i]): break
                    if j == i - 1: return len(word)
        
        return -1