Longest Uncommon Subsequence II - Video Solutions
Longest Uncommon Subsequence II | Leetcode 522 | Live Coding session 🔥🔥🔥🔥
Longest Uncommon Subsequence II - Video Solution
Watch 10 video solutions for Longest Uncommon Subsequence II, a medium level problem involving Array, Hash Table, Two Pointers. This walkthrough by Coding Decoded has 4,798 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Problem Statement
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 <= 501 <= strs[i].length <= 10strs[i]consists of lowercase English letters.
Approach Overview
Problem Overview: You receive an array of strings and must return the length of the longest string that is not a subsequence of any other string in the array. If every string can be formed as a subsequence of another, the answer is -1. The challenge is efficiently verifying subsequence relationships across multiple strings.
Approach 1: Brute Force Check (O(n^2 * L) time, O(1) space)
Check every string against every other string and test whether it appears as a subsequence. For each pair, run a subsequence check using two pointers: move one pointer through the candidate string and another through the potential parent string while matching characters. If a string is not a subsequence of any other string, it is an uncommon subsequence candidate. Track the maximum length among valid candidates.
This method directly models the definition of the problem. With n strings and maximum length L, each subsequence comparison costs O(L), and you perform up to n^2 comparisons. The approach is straightforward and useful for understanding the mechanics of subsequence matching in string problems.
Approach 2: Sorted Length Check (O(n^2 * L) time, O(n) space)
A better strategy is to process longer strings first. Sort the input array in descending order by length using sorting. The first string that is not a subsequence of any other string must be the answer because no later string can be longer.
After sorting, iterate through each string and check whether it is a subsequence of any other string. Use the same two‑pointer subsequence check. A small optimization is handling duplicates with a hash table: if a string appears multiple times, it cannot be uncommon because identical strings are subsequences of each other. Skip those early to reduce unnecessary comparisons.
The key insight is that once you encounter a valid uncommon subsequence while scanning from longest to shortest, you can immediately return its length. This avoids evaluating shorter candidates and reduces practical runtime even though the theoretical complexity remains O(n^2 * L).
Recommended for interviews: The sorted length approach is what most interviewers expect. Starting with brute force shows you understand the definition of subsequences and pairwise comparison. Moving to the sorted strategy demonstrates optimization thinking: process candidates in descending length order and exit early once a valid uncommon subsequence appears.
Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Check | O(n^2 * L) | O(1) | When implementing the simplest interpretation of the problem or during initial reasoning in interviews |
| Sorted Length Check | O(n^2 * L) | O(n) | General optimized approach; process longest strings first and exit early when a valid uncommon subsequence is found |