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.In #521 Longest Uncommon Subsequence I, you are given two strings and must find the length of the longest subsequence that appears in one string but not in the other. The key observation is that if the two strings are exactly the same, then every subsequence of one string will also exist in the other, meaning there is no uncommon subsequence. In this case, the result is -1.
If the strings are different, the solution becomes straightforward. The longer string itself cannot be a subsequence of the shorter one, making it automatically an uncommon subsequence. Therefore, the answer is simply the maximum length of the two strings.
This approach relies on comparing the two strings and evaluating their lengths. Since we only perform a string comparison and basic length checks, the algorithm is efficient and avoids complex subsequence generation.
The overall complexity is linear with respect to the string length due to the equality comparison.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Compare strings and return max length if different | O(n) | O(1) |
NeetCode
Use these hints if you're stuck. Try solving on your own first.
Think very simple.
If <code>a == b</code>, the answer is -1.
Otherwise, the answer is the string <code>a</code> or the string <code>b</code>.
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.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.
1#include <stdio.h>
2#include <string.h>
3
4int findLUSlength(char * a, char * b) {
5
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.
Another approach is to analyze the problem by considering the entire strings as potential subsequences and determine their existence in the other string.
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.
1
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, this problem or its variations can appear in coding interviews, especially as an introductory string problem. It tests a candidate's ability to identify simple observations and avoid overcomplicating the solution.
No special data structure is required for this problem. A direct comparison of the two input strings and checking their lengths is sufficient to determine the result efficiently.
The optimal approach is based on a simple observation. If both strings are identical, there is no uncommon subsequence, so the answer is -1. If they differ, the longer string itself cannot be a subsequence of the other, so the answer is the maximum length of the two strings.
If two strings are different, the longer string cannot fully appear as a subsequence inside the shorter string. That guarantees it is an uncommon subsequence, making its length the correct answer.
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.