Longest Uncommon Subsequence II - Solution & Explanation
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.
Approach 1: Brute Force Check
This approach involves iterating through every string in the array and checking if it is a subsequence of any other string. If a string is a subsequence of no other string, we note its length and update our longest uncommon subsequence length.
For a given string, iterating over all other strings and checking if the current string can be a subsequence can be done using a helper function.
In this C solution, we define a helper function isSubsequence to check if one string is a subsequence of another. The main function findLUSlength iterates over each string, using the helper function to check subsequence relationships. If a string is not a subsequence of any other, its length is considered for the maximum length.
Complexity
Time Complexity: O(n^2 * l) where n is the number of strings and l is the maximum length of a string. Space Complexity: O(1) as we use only constant extra space.
Approach 2: Sorted Length Check
This approach builds upon sorting the strings based on their length in descending order. The idea is to try longer strings first, as they have a better chance of being unique. The process involves checking if the current string is a subsequence of any other strings.
This C solution sorts the strings in descending order of length using the qsort function. Then, it checks each string to see if it's not a subsequence of any other string. The function stops once it finds such a string, returning its length.
Complexity
Time Complexity: O(n^2 * l) with an added O(n log n) for sorting. Space Complexity: O(1), constant extra space is used.
Approach 3: 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.
To determine if string s is unique, we only need to take string s itself and compare it with other strings in the list. If there exists a string for which s is a subsequence, then s is not unique. Otherwise, string s is unique. We take the longest string among all unique strings.
The time complexity is O(n^2 times m), where n is the length of the list of strings, and m is the average length of the strings. The space complexity is O(1).
Code
Python
Java
C++
Go
TypeScript
Complexity Comparison
| Approach | Complexity |
|---|---|
| Brute Force Check | Time Complexity: O(n^2 * l) where n is the number of strings and l is the maximum length of a string. Space Complexity: O(1) as we use only constant extra space. |
| Sorted Length Check | Time Complexity: O(n^2 * l) with an added O(n log n) for sorting. Space Complexity: O(1), constant extra space is used. |
| Subsequence Judgment | — |
Detailed 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 |
Video Solution
Longest Uncommon Subsequence II | Leetcode 522 | Live Coding session 🔥🔥🔥🔥 • Coding Decoded • 4,798 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Longest Uncommon Subsequence II easy or hard?
How to solve Longest Uncommon Subsequence II in O(n)?
What is the best approach for Longest Uncommon Subsequence II?
What data structure is used in Longest Uncommon Subsequence II?
What is the time complexity of Longest Uncommon Subsequence II?
Longest Uncommon Subsequence II Python or Java solution approach?
Is Longest Uncommon Subsequence II asked at Google, Amazon, or Meta?
Ready to solve this problem?
Practice Longest Uncommon Subsequence II with our built-in code editor and test cases.
Practice on FleetCode