Longest Uncommon Subsequence I

Easy
1742.

Longest Uncommon Subsequence I

Longest Uncommon Subsequence I is an easy coding problem on strings and brainteaser, asked in Amazon and Google interviews.

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 <= 100
  • a and b consist of lowercase English letters
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {string} a
 * @param {string} b
 * @return {number}
 */
var findLUSlength = function(a, b) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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 <= 100
  • a and b consist of lowercase English letters

Hints for Longest Uncommon Subsequence I

  1. Hint 1

    Can a whole string be an uncommon subsequence? When is a itself not a subsequence of b?

  2. 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.

  3. Hint 3

    So the answer is max(len(a), len(b)) unless a == 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

  1. If a == b, return -1.
  2. 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