Longest Uncommon Subsequence I

Problem Statement

When provided with two strings a and b, the challenge is to find the length of the longest subsequence that is present in one string but not the other. This type of subsequence is termed as the longest uncommon subsequence. If both strings are identical or share all subsequences, the function should return -1. The core of this problem is determining a subsequence that uniquely belongs to one of the strings and not shared between the two.

Examples

Example 1

Input:

a = "aba", b = "cdc"

Output:

3

Explanation:

One longest uncommon subsequence is "aba" because "aba" is a subsequence of "aba" but not "cdc".
Note that "cdc" is also a longest uncommon subsequence.

Example 2

Input:

a = "aaa", b = "bbb"

Output:

3

Explanation:

The longest uncommon subsequences are "aaa" and "bbb".

Example 3

Input:

a = "aaa", b = "aaa"

Output:

-1

Explanation:

Every subsequence of string a is also a subsequence of string b. Similarly, every subsequence of string b is also a subsequence of string a. So the answer would be `-1`.

Constraints

• 1 <= a.length, b.length <= 100
• a and b consist of lower-case English letters.

Approach and Intuition

In unraveling the problem of finding the longest uncommon subsequence, let us break down the provided examples and constraints:

Decision Strategy

1. If a == b: All subsequences are shared. Return -1.

2. If a != b: The longer of the two strings must have at least one subsequence that is not in the other. Return max(len(a), len(b)).

This simple comparison-based logic works because a full string is always a valid subsequence of itself. If it's not fully equal to the other string, it can't be a subsequence of the other unless it matches exactly, making the problem solvable in constant time.

Solutions

class Solution {
public:
    int longestUncommonSubsequenceLength(string x, string y) {
        if (x == y) {
            return -1;
        } else {
            return max(x.size(), y.size());
        }
    }
};