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.Longest Uncommon Subsequence II asks you to find the longest string in an array that is not a subsequence of any other string. A practical strategy is to compare each string with all others and verify whether it can appear as a subsequence elsewhere.
A common approach is to sort the strings by length in descending order. This ensures that once a valid uncommon subsequence is found, its length is automatically the maximum possible. For each candidate string, check if it is a subsequence of any other string using a two‑pointer subsequence check. If it is not a subsequence of any other string, return its length immediately.
To optimize comparisons, you can also track duplicate strings using a hash table, since duplicates cannot be uncommon subsequences. The subsequence verification runs in linear time relative to the string length, and overall comparisons dominate the complexity.
The main idea is careful pairwise comparison combined with sorting and two‑pointer scanning to efficiently identify the longest valid candidate.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Sorting + pairwise subsequence check | O(n^2 * L) | O(1) to O(n) |
CrioDo
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, variations of subsequence and string comparison problems appear in FAANG and other top tech interviews. This problem tests understanding of subsequences, string manipulation, and optimization through sorting and efficient comparisons.
Arrays are used to store the input strings, while a hash table can help track duplicate strings. The main comparison uses two-pointer traversal to check subsequence relationships between strings.
The typical approach sorts strings by length in descending order and checks whether each string is a subsequence of any other string. A two-pointer technique is used for efficient subsequence checking. The first valid string that is not a subsequence of others gives the answer.
Sorting by length ensures that longer candidates are checked first. As soon as a string is found that is not a subsequence of any other, its length must be the maximum possible, allowing an early return.