LeetCode 521: Longest Uncommon Subsequence I

Problem Restatement

We are given two strings:

a
b

We need to find the length of the longest uncommon subsequence between them.

A subsequence is formed by deleting zero or more characters without changing the order of the remaining characters.

An uncommon subsequence is a subsequence that appears in one string but not the other.

If no uncommon subsequence exists, return:

-1

The official problem asks for the longest uncommon subsequence between two strings. The strings contain lowercase English letters and have length up to 100. (leetcode.com)

Input and Output

Function shape:

class Solution:
    def findLUSlength(self, a: str, b: str) -> int:
        ...

Examples

Example 1:

a = "aba"
b = "cdc"

The strings are different.

The full string "aba" is not a subsequence of "cdc".

Similarly, "cdc" is not a subsequence of "aba".

So the longest uncommon subsequence length is:

3

Example 2:

a = "aaa"
b = "aaa"

The strings are identical.

Every subsequence of one string is also a subsequence of the other.

So no uncommon subsequence exists.

The answer is:

-1

First Thought: Generate Subsequences

A direct idea is:

1. Generate all subsequences of a
2. Generate all subsequences of b
3. Find the longest subsequence appearing in exactly one string

However, a string of length n has:

2^n

subsequences.

This becomes unnecessary for this problem.

Key Insight

There are only two cases.

Case 1: The strings are equal

If:

a == b

then every subsequence of a also exists in b, and vice versa.

So there is no uncommon subsequence.

Return:

-1

Case 2: The strings are different

Suppose:

a != b

Then the entire longer string itself is already an uncommon subsequence.

Why?

Because a string is always a subsequence of itself.

But if the two strings are different, then one full string cannot equal the other full string.

So the longer full string is guaranteed not to be a subsequence of the shorter string.

If the lengths are equal but the strings differ, then either full string is an uncommon subsequence of the other.

Therefore the answer is simply:

max(len(a), len(b))

when the strings are different.

Algorithm

1. If:

   a == b
   return -1
2. Otherwise:

   return max(len(a), len(b))

Correctness

If a == b, then the two strings have exactly the same set of subsequences. Therefore no subsequence can appear in one string without also appearing in the other. So the correct answer is -1.

Now assume a != b.

If the lengths are different, then the longer string cannot be a subsequence of the shorter string because subsequences cannot be longer than the original string. Therefore the longer full string is an uncommon subsequence.

If the lengths are equal but the strings differ, then neither full string equals the other. A string of equal length can only be a subsequence of another string if the two strings are identical. Therefore each full string is not a subsequence of the other.

In both cases, an uncommon subsequence exists whose length equals:

max(len(a), len(b))

No longer subsequence is possible because a subsequence cannot exceed the original string length.

Therefore the algorithm returns the correct answer.

Complexity

Here:

Implementation

class Solution:
    def findLUSlength(self, a: str, b: str) -> int:
        if a == b:
            return -1

        return max(len(a), len(b))

Code Explanation

First compare the strings:

if a == b:

If they are identical, no uncommon subsequence exists:

return -1

Otherwise, the longer full string itself is an uncommon subsequence:

return max(len(a), len(b))

Testing

def test_find_lus_length():
    s = Solution()

    assert s.findLUSlength("aba", "cdc") == 3
    assert s.findLUSlength("aaa", "aaa") == -1
    assert s.findLUSlength("abc", "ab") == 3
    assert s.findLUSlength("a", "b") == 1
    assert s.findLUSlength("abcd", "abc") == 4

    print("all tests passed")

Test meaning: