LeetCode 522: Longest Uncommon Subsequence II

Problem Restatement

We are given an array of strings strs.

We need to 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 any other string in the array.

If no such subsequence exists, return -1.

The official problem asks for the length of the longest uncommon subsequence among an array of strings. If it does not exist, return -1.

Input and Output

Function shape:

class Solution:
    def findLUSlength(self, strs: List[str]) -> int:
        ...

Examples

Example 1:

strs = ["aba", "cdc", "eae"]

Each string has length 3.

None of these full strings is a subsequence of another full string.

So one valid longest uncommon subsequence is:

aba

Its length is:

3

The answer is:

3

Example 2:

strs = ["aaa", "aaa", "aa"]

The string "aaa" appears twice.

So "aaa" is not uncommon.

The string "aa" is a subsequence of "aaa".

So "aa" is not uncommon either.

No uncommon subsequence exists.

The answer is:

-1

First Thought: Generate All Subsequences

A direct approach is to generate every subsequence of every string and count where it appears.

But a string of length m has:

2^m

subsequences.

Even though the constraints are small, this approach is awkward and unnecessary.

We can use a stronger observation.

Key Insight

If a string s is not a subsequence of any other string in strs, then s itself is an uncommon subsequence.

That is enough because the full string is always the longest subsequence of itself.

So instead of generating smaller subsequences, we only need to test each full string.

For each strs[i], ask:

Is strs[i] a subsequence of any strs[j] where i != j?

If the answer is no, then strs[i] is a candidate.

Return the maximum candidate length.

Subsequence Check

To check whether string small is a subsequence of string large, use two pointers.

Move through large.

Whenever characters match, advance the pointer in small.

If we match all characters of small, then it is a subsequence.

def is_subsequence(small: str, large: str) -> bool:
    i = 0

    for ch in large:
        if i < len(small) and small[i] == ch:
            i += 1

    return i == len(small)

Algorithm

Initialize:

answer = -1

For every index i:

1. Let candidate = strs[i].
2. Compare it with every other string strs[j].
3. If candidate is a subsequence of any strs[j] where i != j, it is not uncommon.
4. If it is not a subsequence of any other string, update:

   answer = max(answer, len(candidate))

Return answer.

Correctness

Consider any string strs[i].

If it is not a subsequence of any other string in the array, then strs[i] itself appears as a subsequence of one string, namely itself, and does not appear as a subsequence of any other string. Therefore it is an uncommon subsequence.

If strs[i] is a subsequence of some other string, then strs[i] cannot be used as an uncommon subsequence. Any subsequence of strs[i] is also a subsequence of that other string, so no subsequence derived from strs[i] can be uncommon because of strs[i].

The algorithm checks every string as a candidate and keeps the largest candidate length that is not a subsequence of any other string.

Therefore the returned value is exactly the length of the longest uncommon subsequence. If no candidate exists, the answer remains -1, which is correct.

Complexity

Let:

Implementation

from typing import List

class Solution:
    def findLUSlength(self, strs: List[str]) -> int:
        def is_subsequence(small: str, large: str) -> bool:
            i = 0

            for ch in large:
                if i < len(small) and small[i] == ch:
                    i += 1

            return i == len(small)

        answer = -1
        n = len(strs)

        for i in range(n):
            uncommon = True

            for j in range(n):
                if i == j:
                    continue

                if is_subsequence(strs[i], strs[j]):
                    uncommon = False
                    break

            if uncommon:
                answer = max(answer, len(strs[i]))

        return answer

Code Explanation

The helper function checks whether one string is a subsequence of another:

def is_subsequence(small: str, large: str) -> bool:

The pointer i tracks how many characters of small have been matched:

i = 0

For each character in large, we advance i only on a match:

if i < len(small) and small[i] == ch:
    i += 1

If all characters were matched, return True:

return i == len(small)

Now test every string as a candidate:

for i in range(n):

Assume it is uncommon first:

uncommon = True

Compare it against every other string:

for j in range(n):

Skip itself:

if i == j:
    continue

If it is a subsequence of another string, it is not uncommon:

if is_subsequence(strs[i], strs[j]):
    uncommon = False
    break

If it survives all comparisons, update the answer:

answer = max(answer, len(strs[i]))

Testing

def test_find_lus_length():
    s = Solution()

    assert s.findLUSlength(["aba", "cdc", "eae"]) == 3
    assert s.findLUSlength(["aaa", "aaa", "aa"]) == -1
    assert s.findLUSlength(["aabbcc", "aabbcc", "cb"]) == 2
    assert s.findLUSlength(["abc", "def", "abcd"]) == 4
    assert s.findLUSlength(["a", "b", "c"]) == 1

    print("all tests passed")

Test meaning: