Longest Uncommon Subsequence I

Easy

#0506Time: O(L_a * 2^|a| + L_b * 2^|b|). Generating all subsequences for a string of length n takes exponential time. For each string, there are 2^n subsequences, and creating/hashing them takes time proportional to their lengths.Space: O(L_a * 2^|a| + L_b * 2^|b|), where |s| is the length of string s and L_s is the total length of all subsequences of s. This is because we need to store all 2^n subsequences for each string.

Data structures

String

Prompt

Given two strings a and b, return the length of the longest uncommon subsequence between a and b. If no such uncommon subsequence exists, return -1.

An uncommon subsequence between two strings is a string that is a subsequence of exactly one of them.

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:

-1

Constraints:

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

Approaches

3 approaches with complexity analysis and trade-offs.

This approach involves generating every possible subsequence for both strings, a and b. We can store these subsequences in two separate sets to handle duplicates. Then, we iterate through each set and find a subsequence that does not exist in the other set. The length of the longest such subsequence is our answer.

Algorithm

Create two hash sets, setA and setB, to store the subsequences of strings a and b.
Implement a recursive helper function generateSubsequences(String s, int index, StringBuilder current, Set<String> set) to find all 2^n - 1 non-empty subsequences of s and add them to the given set.
Call this function for both a and b to populate setA and setB.
Initialize a variable maxLength to -1.
Iterate through each subsequence sub in setA. If sub is not present in setB, update maxLength = Math.max(maxLength, sub.length()).
Iterate through each subsequence sub in setB. If sub is not present in setA, update maxLength = Math.max(maxLength, sub.length()).
Return maxLength.

Walkthrough

This method is a direct, albeit naive, translation of the problem's definition into code. It exhaustively generates all subsequences for both input strings and then compares the resulting sets of subsequences to find one that is unique to its original string. The longest such unique subsequence's length is the result.

1import java.util.HashSet;2import java.util.Set;3 4class Solution {5    public int findLUSlength(String a, String b) {6        Set<String> setA = new HashSet<>();7        generateSubsequences(a, 0, new StringBuilder(), setA);8        9        Set<String> setB = new HashSet<>();10        generateSubsequences(b, 0, new StringBuilder(), setB);11        12        int maxLength = -1;13        for (String s : setA) {14            if (!setB.contains(s)) {15                maxLength = Math.max(maxLength, s.length());16            }17        }18        19        for (String s : setB) {20            if (!setA.contains(s)) {21                maxLength = Math.max(maxLength, s.length());22            }23        }24        25        return maxLength;26    }27 28    private void generateSubsequences(String s, int index, StringBuilder current, Set<String> set) {29        if (index == s.length()) {30            if (current.length() > 0) {31                set.add(current.toString());32            }33            return;34        }35        36        // Case 1: Exclude the character at the current index37        generateSubsequences(s, index + 1, current, set);38        39        // Case 2: Include the character at the current index40        current.append(s.charAt(index));41        generateSubsequences(s, index + 1, current, set);42        current.deleteCharAt(current.length() - 1); // Backtrack43    }44}

Complexity

Time

O(L_a * 2^|a| + L_b * 2^|b|). Generating all subsequences for a string of length n takes exponential time. For each string, there are 2^n subsequences, and creating/hashing them takes time proportional to their lengths.

Space

O(L_a * 2^|a| + L_b * 2^|b|), where |s| is the length of string s and L_s is the total length of all subsequences of s. This is because we need to store all 2^n subsequences for each string.

Trade-offs

Pros

It's a straightforward implementation based on the problem definition.
Guaranteed to be correct if it could run within time and memory limits.

Cons

Extremely inefficient in both time and space.
Not feasible for the given constraints and will result in a 'Time Limit Exceeded' or 'Memory Limit Exceeded' error.

This approach improves on the first one by avoiding the massive space complexity. Instead of generating and storing all subsequences beforehand, we generate subsequences for one string and, for each one, immediately check if it's also a subsequence of the other string. This avoids storing the entire, potentially huge, set of subsequences.

Algorithm

Initialize maxLength = -1.
Write a recursive function generateAndCheck that generates all subsequences of a source string.
Inside this function, for each generated subsequence, immediately check if it is a subsequence of the target string using a helper function isSubsequence().
If it is NOT a subsequence of target, update maxLength with the length of the current subsequence if it's greater.
Call generateAndCheck twice: once with a as the source and b as the target, and once with b as the source and a as the target.
The isSubsequence(sub, text) helper can be implemented with two pointers in O(|text|) time.
Return the final maxLength.

Walkthrough

While this method is more space-efficient, it remains computationally expensive. We generate every subsequence of a and check its validity against b, then do the same for subsequences of b against a. The check for whether one string is a subsequence of another is efficient, but performing this check for an exponential number of subsequences is the bottleneck.

1class Solution {2    private int maxLength = -1;3 4    public int findLUSlength(String a, String b) {5        // Check subsequences of 'a' against 'b'6        generateAndCheck(a, 0, new StringBuilder(), b);7        // Check subsequences of 'b' against 'a'8        generateAndCheck(b, 0, new StringBuilder(), a);9        return maxLength;10    }11 12    private void generateAndCheck(String source, int index, StringBuilder current, String target) {13        if (index == source.length()) {14            if (current.length() > 0) {15                if (!isSubsequence(current.toString(), target)) {16                    maxLength = Math.max(maxLength, current.length());17                }18            }19            return;20        }21 22        // Exclude current character23        generateAndCheck(source, index + 1, current, target);24 25        // Include current character26        current.append(source.charAt(index));27        generateAndCheck(source, index + 1, current, target);28        current.deleteCharAt(current.length() - 1); // backtrack29    }30 31    private boolean isSubsequence(String s1, String s2) {32        int i = 0, j = 0;33        while (i < s1.length() && j < s2.length()) {34            if (s1.charAt(i) == s2.charAt(j)) {35                i++;36            }37            j++;38        }39        return i == s1.length();40    }41}

Complexity

Time

O(|b| * 2^|a| + |a| * 2^|b|). For each of the 2^|a| subsequences of `a`, we perform a check against `b` which takes O(|b|) time. The same logic applies for string `b`.

Space

O(max(|a|, |b|)). The space is dominated by the recursion depth for generating subsequences and the `StringBuilder` used to construct them.

Trade-offs

Pros

More space-efficient than the first brute-force approach.
Still follows the problem definition logically.

Cons

The time complexity is still exponential, making it too slow for the given constraints.
It will receive a 'Time Limit Exceeded' verdict on most platforms.

This problem, despite its phrasing, can be solved with a very simple logical deduction. The key insight is to consider the strings a and b themselves as potential subsequences. This observation allows us to bypass any complex subsequence generation or checking, leading to a highly efficient solution.

Algorithm

Compare string a and string b for equality.
If a.equals(b), it means any subsequence of a is also a subsequence of b, and vice versa. No uncommon subsequence can exist. Return -1.
If a and b are not equal, the longer of the two strings is guaranteed to be an uncommon subsequence. This is because a string is always a subsequence of itself, and it cannot be a subsequence of a shorter string. If the lengths are equal, since the strings are different, one cannot be a subsequence of the other. Therefore, the answer is the length of the longer string.
Return Math.max(a.length(), b.length()).

Walkthrough

The core logic relies on analyzing two simple cases:

Strings are identical (a.equals(b)): If the strings are the same, any subsequence of a is also a subsequence of b. No uncommon subsequence exists. The result must be -1.
Strings are different (!a.equals(b)): In this scenario, the longer of the two strings is a guaranteed uncommon subsequence.
- If a.length() > b.length(), a is a subsequence of itself but cannot be a subsequence of the shorter string b. Thus, a is an uncommon subsequence. No subsequence can be longer than a itself, so the LUS length is a.length().
- If a.length() == b.length(), since a and b are not equal, a cannot be a subsequence of b. Again, a is an uncommon subsequence of length a.length(), which is the maximum possible.

This simplifies the problem to a single comparison and a length check.

1class Solution {2    public int findLUSlength(String a, String b) {3        // If the strings are identical, any subsequence of one is a subsequence of the other.4        // No uncommon subsequence exists.5        if (a.equals(b)) {6            return -1;7        }8        9        // If the strings are different, the longer string is an uncommon subsequence.10        // A string is a subsequence of itself.11        // The longer string cannot be a subsequence of the shorter string.12        // If lengths are equal but strings are different, one cannot be a subsequence of the other.13        // Therefore, the longer string is a valid uncommon subsequence, and no longer one can exist.14        return Math.max(a.length(), b.length());15    }16}

Complexity

Time

O(min(|a|, |b|)). The `a.equals(b)` method compares characters up to the length of the shorter string or until a mismatch is found. `String.length()` is an O(1) operation.

Space

O(1). No extra space is used beyond the storage for the input strings.

Trade-offs

Pros

Extremely efficient with linear time and constant space complexity.
Simple and elegant implementation.
Correctly identifies the trick/logical nature of the problem.

Cons

The simplicity of the solution can be non-obvious, as the problem statement might mislead one into thinking about more complex subsequence algorithms.

Solutions

Solution

1class Solution {2public3  int findLUSlength(String a, String b) {4    return a.equals(b) ? -1 : Math.max(a.length(), b.length());5  }6}

1class Solution {2public:3  int findLUSlength(string a, string b) {4    return a == b ? -1 : max(a.size(), b.size());5  }6};

1class Solution:2    def findLUSlength(self, a: str, b: str) -> int: return - \3        1 if a == b else max(len(a), len(b))

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem

Solution

1class Solution {2public3  int findLUSlength(String a, String b) {4    return a.equals(b) ? -1 : Math.max(a.length(), b.length());5  }6}

1class Solution {2public:3  int findLUSlength(string a, string b) {4    return a == b ? -1 : max(a.size(), b.size());5  }6};

1class Solution:2    def findLUSlength(self, a: str, b: str) -> int: return - \3        1 if a == b else max(len(a), len(b))

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.