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 <= 100a and b consist of lower-case English letters.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.
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.
a is equal to b, return -1 because all subsequences of a are subsequences of b and vice versa.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.
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.
Another approach is to analyze the problem by considering the entire strings as potential subsequences and determine their existence in the other string.
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.
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.
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).
| Approach | Complexity |
|---|---|
| Direct String Comparison | Time Complexity: O(n) where n is the length of the strings, due to the string comparison. |
| Substring Verification | Time Complexity: O(n + m) where n and m are the lengths of the strings. |
| Quick Thinking | — |
| Approach | Time | Space | When 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 Comparison | O(n) | O(1) | Best approach once you realize identical strings are the only case where no uncommon subsequence exists |
521. Longest Uncommon Subsequence I (Leetcode Easy) • Programming Live with Larry • 3,275 views views
Watch 9 more video solutions →Practice Longest Uncommon Subsequence I with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor