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 I

Number: 521

Difficulty: Easy

Paid? No

Companies: Google

Problem Description

Given two strings a and b, return the length of the longest uncommon subsequence between them. An uncommon subsequence is a subsequence that is a subsequence of one string but not of the other. If no such uncommon subsequence exists, return -1.

Key Insights

  • If both strings are identical, every subsequence of one string is also a subsequence of the other, so the answer is -1.
  • If the strings are different, the longest string itself is an uncommon subsequence.
  • Therefore, when the strings are not equal, the result is the length of the longer string.

Space and Time Complexity

Time Complexity: O(1)
Space Complexity: O(1)

Solution

The solution directly compares the two strings. If they are exactly the same, every subsequence is common, so return -1. Otherwise, the longest uncommon subsequence is the entire string which has the maximum length among the two. This leads to a simple and efficient constant time solution.

Code Solutions

# Function to find the longest uncommon subsequence length between two strings
def findLUSlength(a: str, b: str) -> int:
    # If both strings are identical, then every subsequence is common; return -1.
    if a == b:
        return -1
    # Otherwise, the longer string is the longest uncommon subsequence.
    return max(len(a), len(b))

# Example usage:
if __name__ == "__main__":
    a = "aba"
    b = "cdc"
    print(findLUSlength(a, b))  # Expected output: 3
← Back to All Questions