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.
"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.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.
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.
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.
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.
Time Complexity: O(n^2 * l) with an added O(n log n) for sorting. Space Complexity: O(1), constant extra space is used.
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).
Python
Java
C++
Go
TypeScript
| 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 | — |
| 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 |
Longest Uncommon Subsequence II | Leetcode 522 | Live Coding session 🔥🔥🔥🔥 • Coding Decoded • 4,704 views views
Watch 9 more video solutions →Practice Longest Uncommon Subsequence II with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor