Domain 1EasyCORE

Longest Uncommon Subsequence I

The problem asks us to find the length of the longest uncommon subsequence between two given strings `a` and `b`. An uncommon subsequence is defined as a string that is a subsequence of one but not the other. The task is to return the length of this longest uncommon subsequence, or `-1` if no such subsequence exists.

Domain: Easy•Updated: 2026-08-31
#Algorithms#LeetCode#qwen2.5-coder:14b#String#Brainteaser

521. Longest Uncommon Subsequence I

Model: qwen2.5-coder:14b
Topics: String,Brainteaser
FAANG asked: 1
Acceptance rate: 59.1%


Problem Breakdown

The problem asks us to find the length of the longest uncommon subsequence between two given strings a and b. An uncommon subsequence is defined as a string that is a subsequence of one but not the other. The task is to return the length of this longest uncommon subsequence, or -1 if no such subsequence exists.

Inputs:

  • Two strings a and b.

Outputs:

  • An integer representing the length of the longest uncommon subsequence between a and b, or -1 if none exists.

Implicit Constraints/Edge Cases:

  • If both strings are identical, every subsequence of one is also a subsequence of the other, so the result should be -1.
  • If the strings are different, the longest uncommon subsequence will be the longer string itself, as it cannot be a subsequence of the shorter string.

Intuition

A brute-force approach would involve generating all possible subsequences for both strings and checking which ones are unique to one string. However, this is computationally expensive due to the exponential number of subsequences that can be generated from a string.

The key insight here is that if two strings are identical, there is no uncommon subsequence between them. If they are different, the longest uncommon subsequence will always be the longer of the two strings because the entire string cannot be a subsequence of the other if they differ in length.

Approach

  1. Check if the strings are identical:
    • If a is equal to b, return -1 because there is no uncommon subsequence.
  2. Determine the longest string:
    • If a and b are not identical, compare their lengths.
    • Return the length of the longer string as it will be the longest uncommon subsequence.

Complexity Analysis

  • Time Complexity: O(1) because we only need to check if the strings are equal and determine their lengths.
  • Space Complexity: O(1) because no additional data structures are used beyond a few variables.

Solution

def findLUSlength(a: str, b: str) -> int:
    # If both strings are identical, return -1
    if a == b:
        return -1
    
    # Return the length of the longer string
    return max(len(a), len(b))

Edge Cases Handled

  • Identical Strings: The code correctly returns -1 when a and b are identical.
  • Different Lengths: The code correctly identifies the longest string as the longest uncommon subsequence.
  • Single Character Strings: The code handles cases where both strings are single characters, returning 1 if they differ or -1 if they are the same.