Vultr DocsLatest Content

Longest Uncommon Subsequence I

Updated on 06 June, 2025

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

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

The solution to the "Longest Uncommon Subsequence I" problem is implemented in C++. This code defines a function longestUncommonSubsequenceLength which determines the length of the longest subsequence that is uncommon between two strings x and y.

Check if both strings x and y are identical. If so, return -1 indicating no uncommon subsequence exists. If x and y are not the same, return the length of the longer string, as the entire string itself is the longest uncommon subsequence.

  • Ensure you compare the two strings directly.
  • Utilize the max function to determine which string is longer.
  • This implementation effectively handles cases where one or both strings are empty.
java 
class Solution {
    public int longestUncommonSubsequenceLength(String str1, String str2) {
        if (str1.equals(str2)) {
            return -1;
        } else {
            return Math.max(str1.length(), str2.length());
        }  
    }
}

In the given Java solution for the "Longest Uncommon Subsequence I", the method longestUncommonSubsequenceLength takes two strings, str1 and str2, as parameters. The function checks if these two strings are equal. If they are, it returns -1, indicating that there is no uncommon subsequence. If the strings are not the same, the function returns the length of the longer string between str1 and str2 using Math.max(str1.length(), str2.length()). This method determines the longest length of a string that isn't a subsequence of the other string if they are not identical.

python 
class Solution:
    def longestUncommonSubsequence(self, x: str, y: str) -> int:
        if x == y:
            return -1
        return max(len(x), len(y))

This Python solution resolves the "Longest Uncommon Subsequence I" problem. Follow these guidelines to understand the implemented logic:

  1. Define a class named Solution.
  2. Inside the Solution, define the method longestUncommonSubsequence, which accepts two string parameters, x and y.
  3. Check if strings x and y are identical. If so, return -1, indicating no unique subsequence can be derived from identical strings.
  4. If x and y are not the same, compute the length of both strings. Return the larger of the two lengths, which is the longest possible uncommon subsequence between the two strings.

This method efficiently determines the length of the longest uncommon subsequence or confirms the absence of any uncommon subsequences when the strings are the same.

Comments

No comments yet.