We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Longest Uncommon Subsequence II

Difficulty: Medium

Problem Description

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.

Key Insights

  • An uncommon subsequence must be a subsequence of one string and not a subsequence of any other string in the array.
  • The longest uncommon subsequence will be the longest string in the array that is not equal to any other string in the array.
  • If all strings in the array are the same or if one string is a subsequence of another string, the uncommon subsequence does not exist.

Space and Time Complexity

Time Complexity: O(n^2 * m) where n is the number of strings and m is the maximum length of a string.
Space Complexity: O(1) because we are using a constant amount of extra space.

Solution

To solve the problem, we can follow these steps:

  1. Initialize a variable to keep track of the maximum length of the uncommon subsequence.
  2. Iterate through each string in the array and check if it is a subsequence of any other string.
  3. If a string is not a subsequence of any other string, update the maximum length.
  4. Return the maximum length if found; otherwise, return -1.

We can use a helper function to determine if one string is a subsequence of another by iterating through both strings.

Code Solutions

def is_subsequence(s1, s2):
    it = iter(s2)
    return all(char in it for char in s1)

def find_longest_uncommon_subsequence(strs):
    max_length = -1
    for i in range(len(strs)):
        uncommon = True
        for j in range(len(strs)):
            if i != j and is_subsequence(strs[i], strs[j]):
                uncommon = False
                break
        if uncommon:
            max_length = max(max_length, len(strs[i]))
    return max_length

# Example usage:
print(find_longest_uncommon_subsequence(["aba", "cdc", "eae"]))  # Output: 3
print(find_longest_uncommon_subsequence(["aaa", "aaa", "aa"]))  # Output: -1
← Back to All Questions