Longest Uncommon Subsequence II: Filtering Candidates with Subsequence Checks

Given an array of strings strs, return the length of the longest uncommon subsequence among them. An uncommon subsequence is a string that is a subsequence of one string but not a subsequence of all the other strings. If no such subsequence exists, return -1.

This is LeetCode 522: Longest Uncommon Subsequence II, and it builds directly on the subsequence-checking technique from Is Subsequence. The twist here is that you are working with an array of strings instead of just two, and you need to find which strings are "uncommon" relative to the others.

A few examples:

• strs = ["aba", "cdc", "eae"] returns 3. Each string is unique and not a subsequence of any other, so all three qualify. The longest is length 3.
• strs = ["aaa", "aaa", "aa"] returns -1. Both "aaa" strings are duplicates (each is a subsequence of the other), and "aa" is a subsequence of "aaa". No string qualifies.
• strs = ["aabbcc", "aabbcc", "cb"] returns 2. The two "aabbcc" strings cancel each other out, but "cb" is not a subsequence of "aabbcc", so it qualifies with length 2.

The key insight

The longest uncommon subsequence must be one of the original strings themselves. Why? Any subsequence of a string is either equal to that string or shorter. If a shorter subsequence qualifies, then the full string it came from also qualifies (and is longer). So you never need to generate subsequences at all. You just need to check the original strings.

For each string in the array, ask: "Is this string a subsequence of any other string in the array?" If the answer is no for every other string, then it qualifies as an uncommon subsequence. Among all qualifying strings, return the length of the longest one.

To find the answer faster, sort the strings by length in descending order. Check the longest strings first. The moment you find one that is not a subsequence of any other string, you can return its length immediately, because no shorter string could beat it.

The solution

The helper function is_subseq(s, t) checks whether s is a subsequence of t using two pointers. This is the same technique from Is Subsequence.

def findLUSlength(strs):
    def is_subseq(s, t):
        i = 0
        for c in t:
            if i < len(s) and c == s[i]:
                i += 1
        return i == len(s)

    strs.sort(key=len, reverse=True)
    for i, s in enumerate(strs):
        if all(not is_subseq(s, strs[j]) for j in range(len(strs)) if j != i):
            return len(s)
    return -1

The outer loop iterates through every string. For each string s, the inner check asks: "Is there any other string strs[j] (where j != i) such that s is a subsequence of strs[j]?" If no such string exists, s qualifies. Because we sorted by length descending, the first qualifier we find is guaranteed to be the longest.

Visual walkthrough

Let's trace the algorithm on strs = ["aba", "cdc", "eae"]. All strings have length 3, so the sorted order is unchanged. We check each one in turn.

The algorithm found a qualifying string on the very first candidate. In the worst case, you would check every string against every other string. But sorting by length and returning early makes the common case fast.

Why sorting helps

Without sorting, you might check a short string first, find that it qualifies, and return its length. But a longer qualifying string might exist. You would have to check every string and track the maximum, which is fine but less elegant.

With sorting by descending length, the first qualifying string you find is automatically the answer. You can return immediately without checking the rest. This does not change the worst-case complexity, but it often saves work in practice.

Complexity analysis

Where n is the number of strings and m is the maximum length of a string. For each of the n strings, you compare it against up to n - 1 other strings. Each comparison takes O(m) time using two pointers. The sort takes O(n log n * m) for string comparisons, which is dominated by the O(n^2 * m) pairwise checks.

Space: O(1) extra beyond the input (or O(n) if you count the space used by the sort).

The building blocks

This problem is built on two fundamental techniques.

Subsequence checking with two pointers. The is_subseq helper is the same pattern from Is Subsequence. One pointer walks through the candidate string, the other walks through the target string. When characters match, advance both. When they do not match, advance only the target pointer. If the candidate pointer reaches the end, the candidate is a subsequence.

Candidate filtering with pairwise comparisons. Instead of generating all possible subsequences (exponential), you observe that the answer must be one of the original strings. This reduces the problem to checking each string against all others, which is O(n^2) comparisons. The sorting optimization lets you return early on the first match.

This filtering pattern appears in other problems too. Whenever you are looking for the "best" item in a collection where disqualification depends on pairwise relationships, iterating through candidates in sorted order and checking each one is a clean approach.

Edge cases

All strings are identical. Every string is a subsequence of every other string. No string qualifies. Return -1.

All strings are unique with no shared characters. Every string passes the check. Return the length of the longest one.

A string is a subsequence of a longer string. The shorter string is eliminated because is_subseq(short, long) returns True. The longer string may still qualify if it is not a subsequence of any other string.

Single string in the array. With only one string, there are no other strings to compare against. The all(...) condition is vacuously true (there are no j != i), so the string qualifies. Return its length.

Empty strings. An empty string is a subsequence of every string, so it never qualifies unless all strings are empty (in which case they are all duplicates and return -1).

From understanding to recall

The core insight here, that candidates must be original strings, is the kind of observation that separates quick solvers from slow ones. Once you see it, the implementation follows naturally. But will you see it next time, under pressure, without a hint?

The subsequence check helper is a building block you should be able to write from memory. If you have drilled Is Subsequence, it takes seconds. The outer loop with the all(...) filter is a standard pattern for pairwise elimination. Combining these two bricks gives you the complete solution.

Try writing this solution from scratch tomorrow. The tricky part is remembering to skip j == i in the inner loop and to sort by descending length. Those small details are exactly what spaced repetition is designed to lock in.

Related posts

• Is Subsequence - The two-pointer subsequence check used as the core helper in this problem
• Longest Common Subsequence - A harder subsequence problem using 2D dynamic programming instead of pairwise string comparison
• Longest Uncommon Subsequence I - The simpler version with only two strings, where the answer is based purely on string equality