LC-0522 Medium LeetCode

522. Longest Uncommon Subsequence II

Array Hash Table Two Pointers String Sorting

Read the full problem statement on LeetCode.

Difficulty: medium Acceptance: 43% Topics: Array, Hash Table, Two Pointers, String, Sorting

Reading material

Arrays & Hashing 12 min Two Pointers 9 min Strings 12 min

Reference solution (spoiler · python)

# Time:  O(l * n^2)
# Space: O(1)

class Solution(object):
    def findLUSlength(self, strs):
        """
        :type strs: List[str]
        :rtype: int
        """
        def isSubsequence(a, b):
            i = 0
            for j in xrange(len(b)):
                if i >= len(a):
                    break
                if a[i] == b[j]:
                    i += 1
            return i == len(a)

        strs.sort(key=len, reverse=True)
        for i in xrange(len(strs)):
            all_of = True
            for j in xrange(len(strs)):
                if len(strs[j]) < len(strs[i]):
                    break
                if i != j and isSubsequence(strs[i], strs[j]):
                    all_of = False
                    break
            if all_of:
                return len(strs[i])
        return -1

Solution from kamyu104/LeetCode-Solutions · MIT