# Longest Uncommon Subsequence I
**Difficulty:** EASY
[External](https://leetcode.com/problems/longest-uncommon-subsequence-i)
Canonical: https://scaleengineer.com/dsa/problems/longest-uncommon-subsequence-i
**Data structures:** String
---
## Problem
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:**

**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.

# Approaches
## Brute Force by Generating All Subsequences
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.
**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.
**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.
### Explanation
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.

```java
import java.util.HashSet;
import java.util.Set;

class Solution {
    public int findLUSlength(String a, String b) {
        Set<String> setA = new HashSet<>();
        generateSubsequences(a, 0, new StringBuilder(), setA);
        
        Set<String> setB = new HashSet<>();
        generateSubsequences(b, 0, new StringBuilder(), setB);
        
        int maxLength = -1;
        for (String s : setA) {
            if (!setB.contains(s)) {
                maxLength = Math.max(maxLength, s.length());
            }
        }
        
        for (String s : setB) {
            if (!setA.contains(s)) {
                maxLength = Math.max(maxLength, s.length());
            }
        }
        
        return maxLength;
    }

    private void generateSubsequences(String s, int index, StringBuilder current, Set<String> set) {
        if (index == s.length()) {
            if (current.length() > 0) {
                set.add(current.toString());
            }
            return;
        }
        
        // Case 1: Exclude the character at the current index
        generateSubsequences(s, index + 1, current, set);
        
        // Case 2: Include the character at the current index
        current.append(s.charAt(index));
        generateSubsequences(s, index + 1, current, set);
        current.deleteCharAt(current.length() - 1); // Backtrack
    }
}
```
### 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`.

## Improved Brute Force by Checking Subsequences
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.
**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.
**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.
### Explanation
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.

```java
class Solution {
    private int maxLength = -1;

    public int findLUSlength(String a, String b) {
        // Check subsequences of 'a' against 'b'
        generateAndCheck(a, 0, new StringBuilder(), b);
        // Check subsequences of 'b' against 'a'
        generateAndCheck(b, 0, new StringBuilder(), a);
        return maxLength;
    }

    private void generateAndCheck(String source, int index, StringBuilder current, String target) {
        if (index == source.length()) {
            if (current.length() > 0) {
                if (!isSubsequence(current.toString(), target)) {
                    maxLength = Math.max(maxLength, current.length());
                }
            }
            return;
        }

        // Exclude current character
        generateAndCheck(source, index + 1, current, target);

        // Include current character
        current.append(source.charAt(index));
        generateAndCheck(source, index + 1, current, target);
        current.deleteCharAt(current.length() - 1); // backtrack
    }

    private boolean isSubsequence(String s1, String s2) {
        int i = 0, j = 0;
        while (i < s1.length() && j < s2.length()) {
            if (s1.charAt(i) == s2.charAt(j)) {
                i++;
            }
            j++;
        }
        return i == s1.length();
    }
}
```
### 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`.

## Simple Logical Check (Optimal)
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.
**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.
**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.
### Explanation
The core logic relies on analyzing two simple cases:

1.  **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`.

2.  **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.

```java
class Solution {
    public int findLUSlength(String a, String b) {
        // If the strings are identical, any subsequence of one is a subsequence of the other.
        // No uncommon subsequence exists.
        if (a.equals(b)) {
            return -1;
        }
        
        // If the strings are different, the longer string is an uncommon subsequence.
        // A string is a subsequence of itself.
        // The longer string cannot be a subsequence of the shorter string.
        // If lengths are equal but strings are different, one cannot be a subsequence of the other.
        // Therefore, the longer string is a valid uncommon subsequence, and no longer one can exist.
        return Math.max(a.length(), b.length());
    }
}
```
### 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())`.

# Solutions
### Java

```java
class Solution {
public
  int findLUSlength(String a, String b) {
    return a.equals(b) ? -1 : Math.max(a.length(), b.length());
  }
}

```

### CPP

```cpp
class Solution {
public:
  int findLUSlength(string a, string b) {
    return a == b ? -1 : max(a.size(), b.size());
  }
};

```

### Python

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

```