#522

Medium

auto_awesomeArray scanning plus hash lookup

LeetCode Problem Workspace

Longest Uncommon Subsequence II

Find the longest string in an array that is not a subsequence of any other string, using array scanning and hash checks efficiently.

array hash table two pointers string sorting

Problem Statement

Given an array of strings strs, determine the length of the longest string that is a subsequence of only one string in the array. An uncommon subsequence is a string that appears as a subsequence in one string but not in any other.

A subsequence is formed by deleting zero or more characters from a string without changing the order of the remaining characters. Return -1 if no string satisfies the uncommon subsequence condition.

Examples

Example 1

Input: strs = ["aba","cdc","eae"]

Output: 3

Example details omitted.

Example 2

Input: strs = ["aaa","aaa","aa"]

Output: -1

Example details omitted.

Constraints

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

Solution Approach

Sort Strings by Length Descending

Begin by sorting the array from longest to shortest so that the first valid uncommon subsequence encountered is guaranteed to be the longest. This leverages the array scanning pattern effectively.

Check Subsequences Using Hashing

For each string, use a hash map to record counts and perform subsequence checks against all other strings. If a string is not a subsequence of any other, it is the longest uncommon subsequence.

Return Result Immediately

Once an uncommon subsequence is found, return its length immediately to avoid unnecessary computation. If none exist after scanning all strings, return -1 to indicate failure.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(n^2 * l) where n is the number of strings and l is the maximum string length due to pairwise subsequence checks. Space complexity is O(n * l) for storing strings and hash maps used in the lookup process.

What Interviewers Usually Probe

Asks if you considered sorting strings by length to optimize finding the longest uncommon subsequence.
Checks whether you correctly handle duplicates and identical strings affecting subsequence detection.
Tests understanding of subsequence verification and how to efficiently skip impossible candidates.

Common Pitfalls or Variants

Common pitfalls

Failing to sort strings, leading to returning a shorter uncommon subsequence instead of the longest.
Incorrectly identifying a string as uncommon when it is a subsequence of another, especially with duplicates.
Overlooking edge cases where all strings are identical or nested subsequences exist, resulting in missing the -1 return case.

Follow-up variants

Consider a version where strings contain uppercase letters or digits requiring adjusted hash checks.
Allow extremely long strings requiring optimized two-pointer subsequence verification instead of naive scans.
Find the second-longest uncommon subsequence instead of the longest, changing scan termination logic.

FAQ

What is the primary pattern used in Longest Uncommon Subsequence II?

The main pattern is array scanning combined with hash lookups to verify subsequences efficiently.

How do I handle identical strings in this problem?

Count duplicates with a hash map; a string appearing more than once cannot be an uncommon subsequence.

What is the best approach to check if one string is a subsequence of another?

Use a two-pointer scan comparing characters in order; this ensures correct subsequence verification.

Can Longest Uncommon Subsequence II return -1?

Yes, return -1 if no string is an uncommon subsequence of the others.

How does sorting by string length help solve the problem?

Sorting ensures that the first uncommon subsequence found is the longest, reducing unnecessary comparisons.

terminal

Solution

Solution 1: Subsequence Judgment

We define a function $check(s, t)$ to determine whether string $s$ is a subsequence of string $t$. We can use a two-pointer approach, initializing two pointers $i$ and $j$ to point to the beginning of strings $s$ and $t$ respectively, then continuously move pointer $j$. If $s[i]$ equals $t[j]$, then move pointer $i$. Finally, check if $i$ equals the length of $s$. If $i$ equals the length of $s$, it means $s$ is a subsequence of $t$.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

class Solution:
    def findLUSlength(self, strs: List[str]) -> int:
        def check(s: str, t: str):
            i = j = 0
            while i < len(s) and j < len(t):
                if s[i] == t[j]:
                    i += 1
                j += 1
            return i == len(s)

        ans = -1
        for i, s in enumerate(strs):
            for j, t in enumerate(strs):
                if i != j and check(s, t):
                    break
            else:
                ans = max(ans, len(s))
        return ans

Continue Practicing

#1048 longest string chain #524 longest word in dictionary through deleting #532 k diff pairs in an array