Problem statement

https://leetcode.com/problems/longest-uncommon-subsequence-ii/

Solution

Here we have very small input dimensions, so we can directly find all substrings for all words in O(2^k * k * n) and find the longest one which is unique.

However, there is smarter solution: note, that the longest uncommon subsequence will always be one of our words: because if it is not, if we add some letter to it, it also will be uncommon subsequence. So, what we need to do now is to sort words given their lengths in decreasing order. Then for every word in words iterate over all other words and check if given word is subsequence of some other word. We can check if one word is subsequence of another in linear time, using 0392 Is Subsequence with two pointers.

Complexity

Overall time complexity is O(n^2k) to check each of word and compare it with each other word. Space complexity is O(n*k) to keep all sorted words.

Code

class Solution:
    def findLUSlength(self, words):
        def isSubsequence(s, t):
            t = iter(t)
            return all(c in t for c in s)
 
        words.sort(key = lambda x:-len(x))
        for i, word in enumerate(words):
            if all(not isSubsequence(word, words[j]) for j in range(len(words)) if j != i): 
                return len(word)
        
        return -1