# Longest Uncommon Subsequence II
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/longest-uncommon-subsequence-ii)
Canonical: https://scaleengineer.com/dsa/problems/longest-uncommon-subsequence-ii
**Patterns:** [Two Pointers](https://scaleengineer.com/dsa/patterns/two-pointers)
**Algorithms:** [Sorting](https://scaleengineer.com/algorithms/sorting)
**Data structures:** Array, Hash Table, String
---
## Problem
Given an array of strings `strs`, return _the length of the **longest uncommon subsequence** between them_. If the longest uncommon subsequence does not exist, return `-1`.

An **uncommon subsequence** between an array of strings is a string that is a **subsequence of one string but not the others**.

A **subsequence** of a string `s` is a string that can be obtained after deleting any number of characters from `s`.

* For example, `"abc"` is a subsequence of `"aebdc"` because you can delete the underlined characters in `"aebdc"` to get `"abc"`. Other subsequences of `"aebdc"` include `"aebdc"`, `"aeb"`, and `""` (empty string).

**Example 1:**

**Input:** strs = ["aba","cdc","eae"]
**Output:** 3

**Example 2:**

**Input:** strs = ["aaa","aaa","aa"]
**Output:** -1

**Constraints:**

* `2 <= strs.length <= 50`
* `1 <= strs[i].length <= 10`
* `strs[i]` consists of lowercase English letters.

# Approaches
## Brute-Force Check
This approach is based on the key observation that if an uncommon subsequence exists, the longest one must be one of the strings from the input array itself. This is because if we have an uncommon subsequence `u` which is a subsequence of `strs[i]`, `u` cannot be longer than `strs[i]`. If `strs[i]` itself is uncommon, it would be a better or equal candidate for the LUS. Therefore, we only need to test each input string to see if it's an uncommon subsequence.
**Time:** O(n^2 * L), where `n` is the number of strings and `L` is the maximum length of a string. There are two nested loops iterating through the strings, giving `O(n^2)`. Inside the loops, the `isSubsequence` check takes `O(L)` time. · **Space:** O(1) extra space. We only use a few variables to keep track of the state, not dependent on the input size.
**Pros:** Simple to understand and implement.; Correctly solves the problem without complex data structures.
**Cons:** Inefficient due to `O(n^2)` comparisons, especially for larger inputs.; It doesn't take advantage of properties like string lengths or the potential for early termination, leading to many unnecessary checks.
### Explanation
We iterate through each string `strs[i]` and check if it's a subsequence of any other string `strs[j]` in the array. If it is not a subsequence of any other string, it qualifies as an uncommon subsequence. We keep track of the maximum length of such strings found. To check if a string `s1` is a subsequence of `s2`, we can use a two-pointer technique. We iterate through `s2` with one pointer, and whenever we find a character that matches the current character of `s1` (tracked by a second pointer), we advance the `s1` pointer. If the `s1` pointer reaches the end of the string, `s1` is a subsequence of `s2`.

```java
class Solution {
    public int findLUSlength(String[] strs) {
        int maxLength = -1;
        for (int i = 0; i < strs.length; i++) {
            boolean isUncommon = true;
            for (int j = 0; j < strs.length; j++) {
                if (i == j) {
                    continue;
                }
                if (isSubsequence(strs[i], strs[j])) {
                    isUncommon = false;
                    break;
                }
            }
            if (isUncommon) {
                maxLength = Math.max(maxLength, strs[i].length());
            }
        }
        return maxLength;
    }

    // Helper to check if s1 is a subsequence of s2
    private boolean isSubsequence(String s1, String s2) {
        if (s1.length() > s2.length()) {
            return false;
        }
        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 a variable `maxLength` to -1.
*   Iterate through each string `strs[i]` in the input array `strs` from `i = 0` to `n-1`.
*   For each `strs[i]`, assume it is an uncommon subsequence. We use a flag, say `isUncommon`, initialized to `true`.
*   Check this assumption by comparing `strs[i]` with every other string `strs[j]` in the array (where `j != i`).
*   If `strs[i]` is a subsequence of `strs[j]`, it means `strs[i]` is not uncommon. Set `isUncommon` to `false` and break the inner loop.
*   After the inner loop, if `isUncommon` is still `true`, it means `strs[i]` is not a subsequence of any other string in the array. Therefore, it is an uncommon subsequence. Update `maxLength = max(maxLength, strs[i].length())`.
*   After iterating through all strings, `maxLength` will hold the length of the longest uncommon subsequence found. Return `maxLength`.

## Sorting and Checking with Early Exit
This approach improves upon the brute-force method by sorting the strings by length in descending order. The logic is that if we check longer strings first, the very first string we find that qualifies as an uncommon subsequence must be the longest one. This allows us to terminate the search early and return the result, making it more efficient in the average case.
**Time:** O(n^2 * L). Sorting takes `O(n log n)`. The nested loops take `O(n^2 * L)` in the worst case. The `isSubsequence` check is `O(L)`. The total complexity is dominated by the nested loops. · **Space:** O(n) or O(log n) depending on the implementation of the sorting algorithm. In Java, `Arrays.sort` for objects takes O(n) space.
**Pros:** More efficient on average than the unsorted version due to early exit as soon as the LUS is found.; The logic is clear and directly follows from the problem definition combined with a greedy approach.; Handles duplicate strings correctly without extra logic, as a duplicate string will always be a subsequence of its copy.
**Cons:** The worst-case time complexity remains `O(n^2 * L)`, which occurs when no early exit is possible (e.g., all strings are unique and have the same length).
### Explanation
The algorithm proceeds by first sorting the input array `strs` based on string length in descending order. Then, it iterates through the sorted array. For each string `strs[i]`, it checks if this string is an uncommon subsequence. A string is uncommon if it's a subsequence of itself but not a subsequence of any *other* string in the array. So, for `strs[i]`, we iterate through all other strings `strs[j]` (where `j != i`) and check if `strs[i]` is a subsequence of `strs[j]`. If we find such a `strs[j]`, then `strs[i]` is not uncommon, and we move to the next string in the sorted array. If we check `strs[i]` against all other strings and find it is not a subsequence of any of them, we have found an uncommon subsequence. Because the array is sorted by length, this must be the longest possible one, so we can immediately return its length. If the entire array is processed without finding such a string, it means no uncommon subsequence exists, and we return -1.

```java
import java.util.Arrays;

class Solution {
    public int findLUSlength(String[] strs) {
        Arrays.sort(strs, (a, b) -> b.length() - a.length());

        for (int i = 0; i < strs.length; i++) {
            boolean isUncommon = true;
            for (int j = 0; j < strs.length; j++) {
                if (i == j) {
                    continue;
                }
                // If strs[i] is a subsequence of another string, it's not uncommon.
                // Note: Because of sorting, if strs[j] is shorter, isSubsequence will be false anyway.
                if (isSubsequence(strs[i], strs[j])) {
                    isUncommon = false;
                    break;
                }
            }
            if (isUncommon) {
                return strs[i].length();
            }
        }
        return -1;
    }

    private boolean isSubsequence(String s1, String s2) {
        if (s1.length() > s2.length()) {
            return false;
        }
        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
*   Sort the `strs` array in descending order of string length.
*   For each string `strs[i]` from `i = 0` to `n-1`:
    *   Assume `strs[i]` is uncommon. Let a flag `isUncommon` be `true`.
    *   For each other string `strs[j]` from `j = 0` to `n-1` (where `j != i`):
        *   If `isSubsequence(strs[i], strs[j])` is true, then `strs[i]` is not uncommon. Set `isUncommon = false` and break this inner loop.
    *   If `isUncommon` is still `true` after checking all other strings, we have found the longest uncommon subsequence because of the sorting. Return `strs[i].length()`.
*   If the outer loop completes without returning, it means no uncommon subsequence exists. Return -1.

# Solutions
### Java

```java
class Solution { public int findLUSlength ( String [] strs ) { int ans = - 1 ; for ( int i = 0 , j = 0 , n = strs . length ; i < n ; ++ i ) { for ( j = 0 ; j < n ; ++ j ) { if ( i == j ) { continue ; } if ( check ( strs [ j ], strs [ i ])) { break ; } } if ( j == n ) { ans = Math . max ( ans , strs [ i ]. length ()); } } return ans ; } private boolean check ( String a , String b ) { int j = 0 ; for ( int i = 0 ; i < a . length () && j < b . length (); ++ i ) { if ( a . charAt ( i ) == b . charAt ( j )) { ++ j ; } } return j == b . length (); } }
```

### CPP

```cpp
class Solution { public: int findLUSlength ( vector < string >& strs ) { int ans = - 1 ; for ( int i = 0 , j = 0 , n = strs . size (); i < n ; ++ i ) { for ( j = 0 ; j < n ; ++ j ) { if ( i == j ) continue ; if ( check ( strs [ j ], strs [ i ])) break ; } if ( j == n ) ans = max ( ans , ( int ) strs [ i ]. size ()); } return ans ; } bool check ( string a , string b ) { int j = 0 ; for ( int i = 0 ; i < a . size () && j < b . size (); ++ i ) if ( a [ i ] == b [ j ]) ++ j ; return j == b . size (); } };
```

### Python

```python
class Solution : def findLUSlength ( self , strs : List [ str ]) -> int : def check ( a , b ): i = j = 0 while i < len ( a ) and j < len ( b ): if a [ i ] == b [ j ]: j += 1 i += 1 return j == len ( b ) n = len ( strs ) ans = - 1 for i in range ( n ): j = 0 while j < n : if i == j or not check ( strs [ j ], strs [ i ]): j += 1 else : break if j == n : ans = max ( ans , len ( strs [ i ])) return ans
```