#521

Easy

auto_awesomeString-driven solution strategy

LeetCode Problem Workspace

Longest Uncommon Subsequence I

Determine the length of the longest uncommon subsequence between two strings using a direct string comparison strategy.

Problem Statement

Given two strings a and b, find the length of the longest uncommon subsequence. An uncommon subsequence is defined as a string that appears as a subsequence in exactly one of the two strings, not both.

If both strings are identical, return -1, since every subsequence of one string is also a subsequence of the other. Otherwise, return the length of the longer string, which guarantees the longest uncommon subsequence.

Examples

Example 1

Input: a = "aba", b = "cdc"

Output: 3

One longest uncommon subsequence is "aba" because "aba" is a subsequence of "aba" but not "cdc". Note that "cdc" is also a longest uncommon subsequence.

Example 2

Input: a = "aaa", b = "bbb"

Output: 3

The longest uncommon subsequences are "aaa" and "bbb".

Example 3

Input: a = "aaa", b = "aaa"

Output: -1

Every subsequence of string a is also a subsequence of string b. Similarly, every subsequence of string b is also a subsequence of string a. So the answer would be -1.

Constraints

1 <= a.length, b.length <= 100
a and b consist of lower-case English letters.

Solution Approach

Check Equality First

Compare strings a and b directly. If they are exactly the same, there is no uncommon subsequence, so immediately return -1.

Use the Longer String as Result

If the strings differ, the entire longer string itself is guaranteed to be a longest uncommon subsequence because it cannot be fully a subsequence of the other string.

Return Length

Finally, return the length of the string identified in the previous step. This ensures O(1) space usage and O(n) time where n is the string length.

Complexity Analysis

Metric	Value
Time	O(n)
Space	O(1)

Time complexity is O(n) because a single string comparison suffices, and space complexity is O(1) since no additional data structures are required.

What Interviewers Usually Probe

Expect a string-driven comparison rather than generating all subsequences.
Watch for equal strings where the answer is -1.
Longer strings directly indicate the longest uncommon subsequence when strings differ.

Common Pitfalls or Variants

Common pitfalls

Attempting to enumerate all subsequences, which is unnecessary for this problem.
Confusing the longest common subsequence with the longest uncommon subsequence.
Forgetting to handle identical strings, which must return -1.

Follow-up variants

Longest Uncommon Subsequence II with multiple strings in the input array.
Find the longest uncommon subsequence with character restrictions or special symbols.
Determine the longest uncommon substring instead of subsequence.

FAQ

What is the simplest way to solve Longest Uncommon Subsequence I?

Directly compare the two strings: if equal, return -1; otherwise, return the length of the longer string.

Why is generating all subsequences unnecessary?

Because any differing string itself is already a valid longest uncommon subsequence, covering all possible options.

How do I handle identical strings?

Return -1 since all subsequences are common between identical strings.

Does the order of strings affect the result?

No, the longer string defines the result regardless of which is first.

What pattern does this problem emphasize?

It focuses on the string-driven solution pattern, emphasizing direct comparison over combinatorial subsequence checks.

terminal

Solution

Solution 1: Quick Thinking

If strings `a` and `b` are equal, then they have no special sequences, return `-1`; otherwise, return the length of the longer string.

1

2

3

class Solution:
    def findLUSlength(self, a: str, b: str) -> int:
        return -1 if a == b else max(len(a), len(b))

Continue Practicing

#520 detect capital #522 longest uncommon subsequence ii #524 longest word in dictionary through deleting