Leetcode 521. Longest Uncommon Subsequence I

Problem Explanation

You are given two strings and the task is to find the longest uncommon subsequence from these two strings. A subsequence is a sequence that can be derived from another string by deleting some or no characters without changing the order of the remaining characters. An uncommon subsequence is a subsequence that is present in one string and does not exist in the other string.

If both strings are identical, no uncommon subsequence exists, in this case, the output should be -1. If the strings are different, the longest uncommon subsequence will be the longest string itself because the longest string cannot be a subsequence of the shorter one.

For example, if we have strings "aba" and "cdc", the longest uncommon subsequence is either "aba" or "cdc" which are the strings themselves and the length is 3.

The solution approach here is simple and does not require any complex algorithms. It is a glaring if-else condition. If both strings are exactly identical then return -1 as there will be no uncommon subsequence. Else return the length of the longest string (which will be the longest uncommon subsequence).

Python

1
2python
3class Solution:
4    def findLUSlength(self, a: str, b: str) -> int:
5        # if strings are identical, return -1
6        if a == b:
7            return -1
8        # return length of the longest string
9        else:
10            return max(len(a), len(b)) 

Java

1
2java
3class Solution {
4    public int findLUSlength(String a, String b) {
5        // if strings are identical, return -1
6        if (a.equals(b)) {
7            return -1;
8        }
9        // return length of the longest string
10        else {
11            return Math.max(a.length(), b.length());
12        }
13    }
14}

Javascript

1
2javascript
3class Solution {
4  findLUSlength(a, b) {
5    // if strings are identical, return -1
6    if (a === b) {
7      return -1;
8    }
9    // return length of the longest string
10    else {
11      return Math.max(a.length, b.length);
12    }
13  }
14}

C++

1
2cpp
3class Solution {
4public:
5    int findLUSlength(string a, string b) {
6        // if strings are identical, return -1
7        if (a == b) {
8            return -1;
9        }
10        // return length of the longest string
11        else {
12            return max(a.length(), b.length());
13        }
14    }
15};

C#

1
2csharp
3public class Solution {
4    public int FindLUSlength(string a, string b) {
5        // if strings are identical, return -1
6        if (a == b) {
7            return -1;
8        }
9        // return length of the longest string
10        else {
11            return Math.Max(a.Length, b.Length);
12        }
13    }
14}

This problem revolves around the concept of subsequences and string comparison. As explained above, when the strings are identical, there is no uncommon subsequence, and hence the output is -1. If the strings are different, the longest subsequence which is uncommon can be the longer string itself, thus the length of the longer string is returned.

The classes defined in Python, Java, JavaScript, C++ and C# receive two strings as inputs and return an integer output. Inside the classes, we have the function findLUSlength which carries out the main logic.

In this function, we first check whether the two input strings are identical. If they are identical, there is no uncommon subsequence and therefore, the function returns -1.

However, if the strings are not identical, there exists an uncommon subsequence. In this scenario, the function returns the length of the longer string, which is the longest uncommon subsequence. The length is calculated using the len function in Python, the length function in Java, JavaScript, and C++, and the Length property in C#.

To find the larger of the two lengths, max function is used in Python and C++, and Math.max is used in Java, JavaScript and C#.

For the given strings "aba" and "cdc", both strings are not identical hence the longest uncommon subsequence is either "aba" or "cdc" and the length of this sequence is 3.

This solution approach is very efficient and concise as it involves just an if-else condition and a few basic operations. These solutions can work for larger strings as well with a time complexity of O(1), as they involve only constant time operations (string comparison and length calculation) regardless of the size of the inputs.


Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.


TA 👨‍🏫