Scale Engineer

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
ArrayHash TableString

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.

class Solution {    public int findLUSlength(String[] strs) {        int maxLength = -1;        for (int i = 0; i < strs.length; i++) {            boolean isUncommon = true;            for (int j = 0; j < strs.length; j++) {                if (i == j) {                    continue;                }                if (isSubsequence(strs[i], strs[j])) {                    isUncommon = false;                    break;                }            }            if (isUncommon) {                maxLength = Math.max(maxLength, strs[i].length());            }        }        return maxLength;    }     // Helper to check if s1 is a subsequence of s2    private boolean isSubsequence(String s1, String s2) {        if (s1.length() > s2.length()) {            return false;        }        int i = 0, j = 0;        while (i < s1.length() && j < s2.length()) {            if (s1.charAt(i) == s2.charAt(j)) {                i++;            }            j++;        }        return i == s1.length();    }}

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.

Solutions

class 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 (); } }

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 →

Next problem