Longest Uncommon Subsequence II

The task is to find the longest uncommon subsequence between the given strings in the array strs. An uncommon subsequence is a string that is a subsequence of one string but not the others.

Here’s a strategy to find the longest uncommon subsequence:

1. Sort by Length: First, sort the strings by their length in descending order. We want to check the longest strings first, as an uncommon subsequence from a longer string is likely to be longer.

2. Check Uniqueness: Iterate through the sorted strings, and for each string, check if it is not a subsequence of any other string in the array.

3. Return Length: If an uncommon subsequence is found, return its length.

4. Handle Edge Case: If no uncommon subsequence is found, return -1.

Here’s the code:

 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

class Solution:
    def findLUSlength(self, strs: List[str]) -> int:
        # Function to check if x is a subsequence of y
        def isSubsequence(x: str, y: str) -> bool:
            it = iter(y)
            return all(c in it for c in x)

        # Sort the strings by length in descending order
        strs.sort(key=len, reverse=True)

        # Iterate through the sorted strings
        for i in range(len(strs)):
            # Flag to track if the current string is uncommon
            is_uncommon = True

            # Iterate through other strings and check if the current string is a subsequence of any of them
            for j in range(len(strs)):
                if i != j and isSubsequence(strs[i], strs[j]):
                    is_uncommon = False
                    break

            # If the current string is uncommon, return its length
            if is_uncommon:
                return len(strs[i])

        # If no uncommon subsequence is found, return -1
        return -1

Explanation:

• The isSubsequence function checks if one string is a subsequence of another.
• The strings are sorted by length to prioritize longer strings.
• Nested loops are used to compare each string against the others, ensuring that the current string is not a subsequence of any other string.
• If an uncommon subsequence is found, its length is returned; otherwise, -1 is returned.