Longest Uncommon Subsequence II

Med

#0507Time: O(n^2 * L), where `n` is the number of strings and `L` is the maximum length of a string. There are two nested loops iterating through the strings, giving `O(n^2)`. Inside the loops, the `isSubsequence` check takes `O(L)` time.Space: O(1) extra space. We only use a few variables to keep track of the state, not dependent on the input size.

Patterns

Two Pointers

Algorithms

Sorting

Data structures

Array Hash Table String

Prompt

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 <= 50
1 <= strs[i].length <= 10
strs[i] consists of lowercase English letters.

Approaches

2 approaches with complexity analysis and trade-offs.

This approach is based on the key observation that if an uncommon subsequence exists, the longest one must be one of the strings from the input array itself. This is because if we have an uncommon subsequence u which is a subsequence of strs[i], u cannot be longer than strs[i]. If strs[i] itself is uncommon, it would be a better or equal candidate for the LUS. Therefore, we only need to test each input string to see if it's an uncommon subsequence.

Algorithm

Initialize a variable maxLength to -1.
Iterate through each string strs[i] in the input array strs from i = 0 to n-1.
For each strs[i], assume it is an uncommon subsequence. We use a flag, say isUncommon, initialized to true.
Check this assumption by comparing strs[i] with every other string strs[j] in the array (where j != i).
If strs[i] is a subsequence of strs[j], it means strs[i] is not uncommon. Set isUncommon to false and break the inner loop.
After the inner loop, if isUncommon is still true, it means strs[i] is not a subsequence of any other string in the array. Therefore, it is an uncommon subsequence. Update maxLength = max(maxLength, strs[i].length()).
After iterating through all strings, maxLength will hold the length of the longest uncommon subsequence found. Return maxLength.

Walkthrough

We iterate through each string strs[i] and check if it's a subsequence of any other string strs[j] in the array. If it is not a subsequence of any other string, it qualifies as an uncommon subsequence. We keep track of the maximum length of such strings found. To check if a string s1 is a subsequence of s2, we can use a two-pointer technique. We iterate through s2 with one pointer, and whenever we find a character that matches the current character of s1 (tracked by a second pointer), we advance the s1 pointer. If the s1 pointer reaches the end of the string, s1 is a subsequence of s2.

1class Solution {2    public int findLUSlength(String[] strs) {3        int maxLength = -1;4        for (int i = 0; i < strs.length; i++) {5            boolean isUncommon = true;6            for (int j = 0; j < strs.length; j++) {7                if (i == j) {8                    continue;9                }10                if (isSubsequence(strs[i], strs[j])) {11                    isUncommon = false;12                    break;13                }14            }15            if (isUncommon) {16                maxLength = Math.max(maxLength, strs[i].length());17            }18        }19        return maxLength;20    }21 22    // Helper to check if s1 is a subsequence of s223    private boolean isSubsequence(String s1, String s2) {24        if (s1.length() > s2.length()) {25            return false;26        }27        int i = 0, j = 0;28        while (i < s1.length() && j < s2.length()) {29            if (s1.charAt(i) == s2.charAt(j)) {30                i++;31            }32            j++;33        }34        return i == s1.length();35    }36}

Complexity

Time

O(n^2 * L), where `n` is the number of strings and `L` is the maximum length of a string. There are two nested loops iterating through the strings, giving `O(n^2)`. Inside the loops, the `isSubsequence` check takes `O(L)` time.

Space

O(1) extra space. We only use a few variables to keep track of the state, not dependent on the input size.

Trade-offs

Pros

Simple to understand and implement.
Correctly solves the problem without complex data structures.

Cons

Inefficient due to O(n^2) comparisons, especially for larger inputs.
It doesn't take advantage of properties like string lengths or the potential for early termination, leading to many unnecessary checks.

This approach improves upon the brute-force method by sorting the strings by length in descending order. The logic is that if we check longer strings first, the very first string we find that qualifies as an uncommon subsequence must be the longest one. This allows us to terminate the search early and return the result, making it more efficient in the average case.

Algorithm

Sort the strs array in descending order of string length.
For each string strs[i] from i = 0 to n-1:
- Assume strs[i] is uncommon. Let a flag isUncommon be true.
- For each other string strs[j] from j = 0 to n-1 (where j != i):
  - If isSubsequence(strs[i], strs[j]) is true, then strs[i] is not uncommon. Set isUncommon = false and break this inner loop.
- If isUncommon is still true after checking all other strings, we have found the longest uncommon subsequence because of the sorting. Return strs[i].length().
If the outer loop completes without returning, it means no uncommon subsequence exists. Return -1.

Walkthrough

The algorithm proceeds by first sorting the input array strs based on string length in descending order. Then, it iterates through the sorted array. For each string strs[i], it checks if this string is an uncommon subsequence. A string is uncommon if it's a subsequence of itself but not a subsequence of any other string in the array. So, for strs[i], we iterate through all other strings strs[j] (where j != i) and check if strs[i] is a subsequence of strs[j]. If we find such a strs[j], then strs[i] is not uncommon, and we move to the next string in the sorted array. If we check strs[i] against all other strings and find it is not a subsequence of any of them, we have found an uncommon subsequence. Because the array is sorted by length, this must be the longest possible one, so we can immediately return its length. If the entire array is processed without finding such a string, it means no uncommon subsequence exists, and we return -1.

1import java.util.Arrays;2 3class Solution {4    public int findLUSlength(String[] strs) {5        Arrays.sort(strs, (a, b) -> b.length() - a.length());6 7        for (int i = 0; i < strs.length; i++) {8            boolean isUncommon = true;9            for (int j = 0; j < strs.length; j++) {10                if (i == j) {11                    continue;12                }13                // If strs[i] is a subsequence of another string, it's not uncommon.14                // Note: Because of sorting, if strs[j] is shorter, isSubsequence will be false anyway.15                if (isSubsequence(strs[i], strs[j])) {16                    isUncommon = false;17                    break;18                }19            }20            if (isUncommon) {21                return strs[i].length();22            }23        }24        return -1;25    }26 27    private boolean isSubsequence(String s1, String s2) {28        if (s1.length() > s2.length()) {29            return false;30        }31        int i = 0, j = 0;32        while (i < s1.length() && j < s2.length()) {33            if (s1.charAt(i) == s2.charAt(j)) {34                i++;35            }36            j++;37        }38        return i == s1.length();39    }40}

Complexity

Time

O(n^2 * L). Sorting takes `O(n log n)`. The nested loops take `O(n^2 * L)` in the worst case. The `isSubsequence` check is `O(L)`. The total complexity is dominated by the nested loops.

Space

O(n) or O(log n) depending on the implementation of the sorting algorithm. In Java, `Arrays.sort` for objects takes O(n) space.

Trade-offs

Pros

More efficient on average than the unsorted version due to early exit as soon as the LUS is found.
The logic is clear and directly follows from the problem definition combined with a greedy approach.
Handles duplicate strings correctly without extra logic, as a duplicate string will always be a subsequence of its copy.

Cons

The worst-case time complexity remains O(n^2 * L), which occurs when no early exit is possible (e.g., all strings are unique and have the same length).

Solutions

Solution

1class Solution { public int findLUSlength ( String [] strs ) { int ans = - 1 ; for ( int i = 0 , j = 0 , n = strs . length ; i < n ; ++ i ) { for ( j = 0 ; j < n ; ++ j ) { if ( i == j ) { continue ; } if ( check ( strs [ j ], strs [ i ])) { break ; } } if ( j == n ) { ans = Math . max ( ans , strs [ i ]. length ()); } } return ans ; } private boolean check ( String a , String b ) { int j = 0 ; for ( int i = 0 ; i < a . length () && j < b . length (); ++ i ) { if ( a . charAt ( i ) == b . charAt ( j )) { ++ j ; } } return j == b . length (); } }

1class Solution { public: int findLUSlength ( vector < string >& strs ) { int ans = - 1 ; for ( int i = 0 , j = 0 , n = strs . size (); i < n ; ++ i ) { for ( j = 0 ; j < n ; ++ j ) { if ( i == j ) continue ; if ( check ( strs [ j ], strs [ i ])) break ; } if ( j == n ) ans = max ( ans , ( int ) strs [ i ]. size ()); } return ans ; } bool check ( string a , string b ) { int j = 0 ; for ( int i = 0 ; i < a . size () && j < b . size (); ++ i ) if ( a [ i ] == b [ j ]) ++ j ; return j == b . size (); } };

1class Solution : def findLUSlength ( self , strs : List [ str ]) -> int : def check ( a , b ): i = j = 0 while i < len ( a ) and j < len ( b ): if a [ i ] == b [ j ]: j += 1 i += 1 return j == len ( b ) n = len ( strs ) ans = - 1 for i in range ( n ): j = 0 while j < n : if i == j or not check ( strs [ j ], strs [ i ]): j += 1 else : break if j == n : ans = max ( ans , len ( strs [ i ])) return ans

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem