Skip to main content
Talentd

Longest Uncommon Subsequence I - Solution & Explanation

EasyString13 min readAsked at: Meta, Google
Practice this problem

Problem Statement

Given two strings a and b, return the length of the longest uncommon subsequence between a and b. If no such uncommon subsequence exists, return -1.

An uncommon subsequence between two strings is a string that is a subsequence of exactly one of them.

 

Example 1:

Input: a = "aba", b = "cdc"
Output: 3
Explanation: 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
Explanation: The longest uncommon subsequences are "aaa" and "bbb".

Example 3:

Input: a = "aaa", b = "aaa"
Output: -1
Explanation: 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.

Approach Overview

Problem Overview: Given two strings a and b, return the length of the longest string that is a subsequence of one string but not the other. If both strings are identical, no such subsequence exists and the answer is -1.

Approach 1: Subsequence Verification (O(n + m) time, O(1) space)

The direct interpretation is to verify whether one string is a subsequence of the other. Use a two‑pointer scan: iterate through the larger string while advancing a pointer on the candidate subsequence when characters match. Perform this check twice—once to see if a is a subsequence of b and once for the reverse. If a is not a subsequence of b, then the entire string a itself becomes an uncommon subsequence. The same logic applies to b. This approach demonstrates understanding of subsequence matching using two pointers and basic string traversal.

Approach 2: Direct String Comparison (O(n) time, O(1) space)

The key observation simplifies the problem drastically. If the two strings are exactly equal, every subsequence of one will also appear in the other, so the answer must be -1. If they differ, the longer string itself cannot be a subsequence of the shorter one, which means the entire longer string is the longest uncommon subsequence. You only need a single equality check and a length comparison. This turns what initially looks like a subsequence problem into a simple comparison on string lengths.

Recommended for interviews: Interviewers expect the direct comparison insight. Many candidates initially attempt subsequence checks with two pointers, which works but adds unnecessary logic. Recognizing that identical strings are the only failing case leads to the optimal O(n) solution with constant space. Showing the subsequence verification approach first can demonstrate reasoning, but the direct comparison method shows strong problem‑solving intuition.

Approach 1: Direct String Comparison

This approach takes advantage of the fact that if two strings are identical, there are no uncommon subsequences. If they are different, the longest uncommon subsequence is the longest string itself.

  • If a is equal to b, return -1 because all subsequences of a are subsequences of b and vice versa.
  • If a is not equal to b, return the maximum length of a or b since the longer string itself cannot be a subsequence of the other.

This C solution uses the standard library's strcmp function to check for string equality. If the strings are equal, it returns -1. Otherwise, it uses the strlen function to find the length of the longest string and returns that as the length of the longest uncommon subsequence.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n) where n is the length of the strings, due to the string comparison.
Space Complexity: O(1), no additional space is needed.

Try this approach in the editor →

Approach 2: Substring Verification

Another approach is to analyze the problem by considering the entire strings as potential subsequences and determine their existence in the other string.

  • Check if one string is a subsequence of the other and vice versa.
  • If neither string is a subsequence of the other, return the length of the longest string.
  • If one is a subsequence of the other, then no uncommon subsequence exists, return -1.

This solution defines a helper function isSubsequence that checks if one string is a subsequence of another using two pointers. It then uses this helper in findLUSlength to check the relations between a and b.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n + m) where n and m are the lengths of the strings.
Space Complexity: O(1), since no additional structures are employed.

Try this approach in the editor →

Approach 3: 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.

The time complexity is O(n), where n is the length of the longer string among a and b. The space complexity is O(1).

Code

PythonJavaC++GoTypeScriptRust

Python

Java

C++

Go

TypeScript

Rust

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Direct String Comparison

Time Complexity: O(n) where n is the length of the strings, due to the string comparison.
Space Complexity: O(1), no additional space is needed.

Substring Verification

Time Complexity: O(n + m) where n and m are the lengths of the strings.
Space Complexity: O(1), since no additional structures are employed.

Quick Thinking—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Subsequence Verification (Two Pointers)O(n + m)O(1)When solving the problem directly by checking subsequence relationships between both strings
Direct String ComparisonO(n)O(1)Best approach once you realize identical strings are the only case where no uncommon subsequence exists

Video Solution

521. Longest Uncommon Subsequence I (Leetcode Easy) • Programming Live with Larry • 3,288 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Longest Uncommon Subsequence I easy or hard?
LeetCode classifies this problem as Easy. The challenge comes from recognizing the key observation that identical strings eliminate all uncommon subsequences. Once that insight is clear, the implementation becomes a simple comparison.
Longest Uncommon Subsequence I Python/Java solution
In Python or Java, check if the two strings are equal. If they are equal, return -1. Otherwise return max(len(a), len(b)) in Python or Math.max(a.length(), b.length()) in Java. This concise logic implements the optimal O(n) solution.
How to solve Longest Uncommon Subsequence I in O(n)?
Compare the two input strings directly. If they are identical, return -1 because every subsequence will match in both strings. If they differ, return the maximum of their lengths since the longer string itself cannot be a subsequence of the shorter one. This solution scans the strings once, giving O(n) time complexity.
What is the best approach for Longest Uncommon Subsequence I?
Direct string comparison is the optimal approach. If the two strings are equal, return -1 because every subsequence appears in both. Otherwise, the longer string itself is the longest uncommon subsequence. This runs in O(n) time with O(1) space.
Is Longest Uncommon Subsequence I asked at Google/Amazon/Meta?
Variants of subsequence and string comparison problems frequently appear in interviews at companies like Amazon, Google, and Meta. While this exact question is easier than typical interview problems, it tests understanding of subsequences and recognizing hidden simplifications.
What data structure is used in Longest Uncommon Subsequence I?
The problem mainly uses basic string operations. Some implementations demonstrate subsequence checks using the two-pointer technique on strings, but the optimal solution only requires direct string comparison and length evaluation.
What is the time complexity of Longest Uncommon Subsequence I?
The optimal solution runs in O(n) time where n is the length of the longer string, because it only requires a string equality check and length comparison. Space complexity is O(1) since no additional data structures are required.

Ready to solve this problem?

Practice Longest Uncommon Subsequence I with our built-in code editor and test cases.

Practice on FleetCode
Previous

Longest Uncommon Subsequence II