algoadvance

Leetcode 521. Longest Uncommon Subsequence I

Problem Statement

Given two strings a and b, return the length of the longest uncommon subsequence (LUS) between them. The longest uncommon subsequence is defined as the longest subsequence of one of these strings that is not a subsequence of the other string.

A subsequence is a sequence derived from another sequence by deleting some or no elements without changing the order of the remaining elements. For example, “abc”, “ab”, and “a” are all subsequences of “abc”.

If the longest uncommon subsequence does not exist, return -1.

Example 1:

• Input: a = "aba", b = "cdc"
• Output: 3

Example 2:

• Input: a = "aaa", b = "bbb"
• Output: 3

Example 3:

• Input: a = "aaa", b = "aaa"
• Output: -1

Clarifying Questions

1. Can the strings a and b be empty?
   • No, both strings will be non-empty.
2. What is the maximum length of strings a and b?
   • The maximum length for each string is 100.

Strategy

1. Check if the strings are equal:
   • If a equals b, then there is no uncommon subsequence, return -1.
2. Check if the strings are different:
   • If a is not equal to b, the longest uncommon subsequence will be the longer string itself because it won’t be a subsequence of the other string.
   • If they are of the same length but are different strings, the length of either string can be the LUS as none is a subsequence of the other.

Code

public class Solution {
    public int findLUSlength(String a, String b) {
        if (a.equals(b)) {
            return -1;
        } else {
            return Math.max(a.length(), b.length());
        }
    }
}

Time Complexity

• The time complexity of the findLUSlength function is O(N) where N is the maximum length of the strings a or b. This complexity arises from the equals method which compares the two strings.

Explanation

1. Equality Check:
   • if (a.equals(b)): This checks if both strings are exactly the same.
   • If true, return -1 because there is no uncommon subsequence.
2. Different Strings:
   • return Math.max(a.length(), b.length()): This returns the length of the longer string as the longest uncommon subsequence. If the strings are of equal length but different, it returns that length, because neither string can be a subsequence of the other.

By following this strategy, we ensure that we cover all cases effectively and efficiently.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?