Longest Uncommon Subsequence I — Problem & Solution
Longest Uncommon Subsequence I solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem.
Longest Uncommon Subsequence I is an easy coding problem on strings and brainteaser, asked in Amazon and Google interviews.
- Difficulty: Easy
- Topics: Strings, Brainteaser
- Asked at: Amazon, Google
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
Given two strings a and b, return the length of their longest uncommon subsequence, or -1 if there is none.
An uncommon subsequence of two strings is a string that is a subsequence of exactly one of them. A subsequence is what remains after deleting any number of characters (possibly none) without changing the order of the rest.
Example 1
Input: a = "code", b = "kairo"
Output: 5
Explanation: `"kairo"` is a subsequence of `b` but not of `a`.
Example 2
Input: a = "abc", b = "xbz"
Output: 3
Example 3
Input: a = "aaa", b = "aaa"
Output: -1
Explanation: Every subsequence of one string is a subsequence of the other.
Constraints
1 <= a.length, b.length <= 100a and b consist of lowercase English letters
Hints for Longest Uncommon Subsequence I
Hint 1
Can a whole string be an uncommon subsequence? When is
aitself not a subsequence ofb?Hint 2
If the strings differ, the longer one cannot be a subsequence of the shorter one — and if they have equal length but differ, neither is a subsequence of the other.
Hint 3
So the answer is
max(len(a), len(b))unlessa == b, in which case it is-1.
How to solve Longest Uncommon Subsequence I
A subsequence of a string is never longer than the string, so the best conceivable answer is a whole string — and a whole string works whenever the two strings differ.
Approach
- If
a == b, return-1. - Otherwise return
max(len(a), len(b)).
Why it works
If a != b, take the longer string (either one if the lengths are equal). It cannot be a subsequence of the other: a longer string never fits inside a shorter one, and a string of the same length is a subsequence only of itself. Nothing longer exists, so it is optimal. If a == b, any subsequence of one is a subsequence of the other, so no uncommon subsequence exists.
Complexity
- Time —
O(|a| + |b|) for the comparison - Space —
O(1)
Pitfalls
- Searching subsequences is unnecessary — the problem is a trick question about whole strings.
- Equal lengths do not mean equal strings:
"abc"and"xbz"give 3.
Reference solution
Python
def findLUSlength(a: str, b: str) -> int:
return -1 if a == b else max(len(a), len(b))Java
public static int findLUSlength(String a, String b) {
return a.equals(b) ? -1 : Math.max(a.length(), b.length());
}C++
int findLUSlength(string a, string b) {
return a == b ? -1 : (int) max(a.size(), b.size());
}JavaScript
var findLUSlength = function(a, b) {
return a === b ? -1 : Math.max(a.length, b.length);
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 515 strings problems · the whole catalogue
Learn the technique: Strings