# LeetCode 522: Longest Uncommon Subsequence II

## Problem Restatement

We are given an array of strings `strs`.

We need to return the length of the longest uncommon subsequence among them.

An uncommon subsequence is a string that is a subsequence of one string but not a subsequence of any other string in the array.

If no such subsequence exists, return `-1`.

The official problem asks for the length of the longest uncommon subsequence among an array of strings. If it does not exist, return `-1`.

## Input and Output

| Item | Meaning |
|---|---|
| Input | An array of strings `strs` |
| Output | Length of the longest uncommon subsequence |
| Return `-1` | If no uncommon subsequence exists |
| Subsequence rule | Delete characters without changing order |

Function shape:

```python
class Solution:
    def findLUSlength(self, strs: List[str]) -> int:
        ...
```

## Examples

Example 1:

```python
strs = ["aba", "cdc", "eae"]
```

Each string has length `3`.

None of these full strings is a subsequence of another full string.

So one valid longest uncommon subsequence is:

```text
aba
```

Its length is:

```python
3
```

The answer is:

```python
3
```

Example 2:

```python
strs = ["aaa", "aaa", "aa"]
```

The string `"aaa"` appears twice.

So `"aaa"` is not uncommon.

The string `"aa"` is a subsequence of `"aaa"`.

So `"aa"` is not uncommon either.

No uncommon subsequence exists.

The answer is:

```python
-1
```

## First Thought: Generate All Subsequences

A direct approach is to generate every subsequence of every string and count where it appears.

But a string of length `m` has:

```text
2^m
```

subsequences.

Even though the constraints are small, this approach is awkward and unnecessary.

We can use a stronger observation.

## Key Insight

If a string `s` is not a subsequence of any other string in `strs`, then `s` itself is an uncommon subsequence.

That is enough because the full string is always the longest subsequence of itself.

So instead of generating smaller subsequences, we only need to test each full string.

For each `strs[i]`, ask:

```text
Is strs[i] a subsequence of any strs[j] where i != j?
```

If the answer is no, then `strs[i]` is a candidate.

Return the maximum candidate length.

## Subsequence Check

To check whether string `small` is a subsequence of string `large`, use two pointers.

Move through `large`.

Whenever characters match, advance the pointer in `small`.

If we match all characters of `small`, then it is a subsequence.

```python
def is_subsequence(small: str, large: str) -> bool:
    i = 0

    for ch in large:
        if i < len(small) and small[i] == ch:
            i += 1

    return i == len(small)
```

## Algorithm

Initialize:

```python
answer = -1
```

For every index `i`:

1. Let `candidate = strs[i]`.
2. Compare it with every other string `strs[j]`.
3. If `candidate` is a subsequence of any `strs[j]` where `i != j`, it is not uncommon.
4. If it is not a subsequence of any other string, update:
   ```python
   answer = max(answer, len(candidate))
   ```

Return `answer`.

## Correctness

Consider any string `strs[i]`.

If it is not a subsequence of any other string in the array, then `strs[i]` itself appears as a subsequence of one string, namely itself, and does not appear as a subsequence of any other string. Therefore it is an uncommon subsequence.

If `strs[i]` is a subsequence of some other string, then `strs[i]` cannot be used as an uncommon subsequence. Any subsequence of `strs[i]` is also a subsequence of that other string, so no subsequence derived from `strs[i]` can be uncommon because of `strs[i]`.

The algorithm checks every string as a candidate and keeps the largest candidate length that is not a subsequence of any other string.

Therefore the returned value is exactly the length of the longest uncommon subsequence. If no candidate exists, the answer remains `-1`, which is correct.

## Complexity

Let:

| Symbol | Meaning |
|---|---|
| `n` | Number of strings |
| `m` | Maximum string length |

| Metric | Value | Why |
|---|---|---|
| Time | `O(n^2 * m)` | Each pair of strings may need one subsequence check |
| Space | `O(1)` | Only counters and flags are stored |

## Implementation

```python
from typing import List

class Solution:
    def findLUSlength(self, strs: List[str]) -> int:
        def is_subsequence(small: str, large: str) -> bool:
            i = 0

            for ch in large:
                if i < len(small) and small[i] == ch:
                    i += 1

            return i == len(small)

        answer = -1
        n = len(strs)

        for i in range(n):
            uncommon = True

            for j in range(n):
                if i == j:
                    continue

                if is_subsequence(strs[i], strs[j]):
                    uncommon = False
                    break

            if uncommon:
                answer = max(answer, len(strs[i]))

        return answer
```

## Code Explanation

The helper function checks whether one string is a subsequence of another:

```python
def is_subsequence(small: str, large: str) -> bool:
```

The pointer `i` tracks how many characters of `small` have been matched:

```python
i = 0
```

For each character in `large`, we advance `i` only on a match:

```python
if i < len(small) and small[i] == ch:
    i += 1
```

If all characters were matched, return `True`:

```python
return i == len(small)
```

Now test every string as a candidate:

```python
for i in range(n):
```

Assume it is uncommon first:

```python
uncommon = True
```

Compare it against every other string:

```python
for j in range(n):
```

Skip itself:

```python
if i == j:
    continue
```

If it is a subsequence of another string, it is not uncommon:

```python
if is_subsequence(strs[i], strs[j]):
    uncommon = False
    break
```

If it survives all comparisons, update the answer:

```python
answer = max(answer, len(strs[i]))
```

## Testing

```python
def test_find_lus_length():
    s = Solution()

    assert s.findLUSlength(["aba", "cdc", "eae"]) == 3
    assert s.findLUSlength(["aaa", "aaa", "aa"]) == -1
    assert s.findLUSlength(["aabbcc", "aabbcc", "cb"]) == 2
    assert s.findLUSlength(["abc", "def", "abcd"]) == 4
    assert s.findLUSlength(["a", "b", "c"]) == 1

    print("all tests passed")
```

Test meaning:

| Test | Why |
|---|---|
| `["aba", "cdc", "eae"]` | Several distinct strings of same length |
| `["aaa", "aaa", "aa"]` | Duplicates remove longer candidates |
| `["aabbcc", "aabbcc", "cb"]` | Short string may be uncommon |
| `["abc", "def", "abcd"]` | Longest string can be answer |
| Single-character strings | Minimum-size candidates |