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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Longest Uncommon Subsequence II

Number: 522

Difficulty: Medium

Paid? No

Companies: Google

Problem Description

Given an array of strings strs, return the length of the longest uncommon subsequence between them. An uncommon subsequence is a string that is a subsequence of one string but not of any of the others in the array. If no such subsequence exists, return -1.

Key Insights

  • A subsequence of a string is formed by deleting zero or more characters without changing the order.
  • If a string appears more than once, it cannot be an uncommon subsequence since it is a subsequence of more than one string.
  • By sorting the strings in descending order by length, checking longer strings first, we can stop as soon as we find a candidate that is not a subsequence of any other string.
  • For each candidate string, compare it with every other string using a two-pointer technique to determine if it is a subsequence.

Space and Time Complexity

Time Complexity: O(n^2 * L) where n is the number of strings and L is the maximum string length (maximum 10). Space Complexity: O(n) for sorting if needed, with additional O(1) auxiliary space.

Solution

We first sort the array of strings in descending order based on their length so that the longest string is considered first. For each string, we then check if it is a subsequence of any other string in the list. The subsequence check is implemented using two pointers: one pointer iterates over the candidate string and the other over the other string. If the candidate appears as a subsequence in any other string, we discard it; otherwise, its length is the answer. Strings with duplicates are automatically discarded because a duplicate string is a subsequence of itself appearing in another position.

Code Solutions

def is_subsequence(s, t):
    # Check if s is a subsequence of t
    it = iter(t)
    return all(ch in it for ch in s)

def findLUSlength(strs):
    # Count occurrences to handle duplicates
    count = {}
    for s in strs:
        count[s] = count.get(s, 0) + 1
        
    # Sort strings by descending length
    strs.sort(key=lambda x: len(x), reverse=True)
    
    # Loop through each string as candidate
    for i, s in enumerate(strs):
        # If string appears more than once, skip as uncommon subsequence candidate
        if count[s] > 1:
            continue
        # Check if s is a subsequence of any other candidate string
        uncommon = True
        for j, t in enumerate(strs):
            if i == j:
                continue
            if len(t) < len(s):
                # No need to check further if the compared string is shorter
                break
            if is_subsequence(s, t):
                uncommon = False
                break
        if uncommon:
            return len(s)
    return -1

# Example usage:
print(findLUSlength(["aba", "cdc", "eae"]))  # Expected output 3
← Back to All Questions