521. Longest Uncommon Subsequence I

EasyString

Problem Description

The task is to find the length of the longest uncommon subsequence between two given strings a and b. An uncommon subsequence is defined as a sequence that can be found as a subsequence in one string but not in the other string.

A subsequence of a string is a series of characters that can be derived from the original string by deleting some or no characters without changing the order of the remaining characters. For instance, "abc" is a subsequence of "aebdc" because you can remove the characters e and d from "aebdc" to get "abc".

The problem asks for the longest sequence that is a subsequence of one string and absolutely not a subsequence of the other string. If no such uncommon subsequence exists between a and b, the function should return -1. The uniqueness of the subsequence is important here; it must be unique to one string only.

Intuition

When looking for the longest uncommon subsequence between the two strings a and b, it's crucial to note that if the strings are identical, there can't be an uncommon subsequence, and we should return -1. This is because any subsequence of a would also be a subsequence of b and vice versa since they are the same.

Now, when the strings are different, the longest uncommon subsequence is actually the longer of the two strings. This is intuitive because a full string cannot be a subsequence of another shorter string. This means if a and b are different, the longest string itself can be considered the longest uncommon subsequence. This is why the provided solution returns the maximum of the lengths of a and b when a does not equal b.

In summary, the crucial insight is to realize that when the strings are not the same, the entire string of the longer one is the longest subsequence that the other string cannot have.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

What is the running time of the following code?

1int sqrt(int n) {
2  for (int guess = 1; guess * guess <= n; guess++) {
3    if (guess * guess == n) {
4      return guess;
5    }
6  }
7  return -1;
8}

O(1)O(log n)O(sqrt(n))O(n)

I don’t know

Solution Approach

The solution involves a very simple approach and does not necessitate complex algorithms or data structures. It leverages fundamental properties of strings and subsequences.

Since a string is always a subsequence of itself and we're looking for the longest uncommon subsequence, the implementation checks for the following conditions:

If a is equal to b, then every subsequence of a is also a subsequence of b and vice versa. Thus, there cannot be an uncommon subsequence, and the function returns -1.
If a is not equal to b, the longest uncommon subsequence can be the longer string itself because the whole string cannot be a subsequence of the shorter string. This guarantees that the longest subsequence is unique to the longer string.

The code snippet provided in the reference solution can be explained in two parts:

1if a == b:
2    return -1
3else:
4    return max(len(a), len(b))

However, this can be simplified into a single line as it is in the solution:

1return -1 if a == b else max(len(a), len(b))

The code includes a conditional expression that returns -1 when a and b are identical (ensuring no uncommon subsequences exist) or it returns the length of the longer of the two strings.

No special patterns or algorithms are needed here since it boils down to a simple comparison and a straightforward application of the definition of a subsequence in the context of string comparison.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Which of the following problems can be solved with backtracking (select multiple)

Generating subsetsGenerating random numbersGenerating permutationsSorting integers

Example Walkthrough

Let's illustrate the solution approach with a small example. Suppose we have two strings a = "horse" and b = "corpus". We want to determine the length of the longest uncommon subsequence between the two strings.

Here are the steps to solve this:

First, we compare the strings a and b to check if they are equal.
Since "horse" is not equal to "corpus", we proceed to the next condition.
According to our approach, the longer of the two strings can be considered the longest uncommon subsequence because one cannot be a subsequence of the other.
We then get the lengths of a and b. For a = "horse", the length is 5. For b = "corpus", the length is 6.
The longest string of the two is "corpus" with a length of 6.
Therefore, the length of the longest uncommon subsequence between "horse" and "corpus" is 6.

In summary, by following the solution approach, the length of the longest uncommon subsequence between a and b is determined by simply comparing the lengths of a and b since they are not identical, resulting in a return value of 6 for this specific example.

Solution Implementation

1class Solution:
2    def findLUSlength(self, str_a: str, str_b: str) -> int:
3        # Check if the two strings are identical
4        if str_a == str_b:
5            # The longest uncommon subsequence does not exist if strings are the same,
6            # hence return -1 as specified by the problem
7            return -1
8        else:
9            # If strings are not the same, return the length of the longer string
10            # since the longer string itself will be the longest uncommon subsequence
11            return max(len(str_a), len(str_b))
12

1public class Solution {
2    // Method to find the length of the Longest Uncommon Subsequence (LUS) between two strings
3    public int findLUSlength(String firstString, String secondString) {
4        // Check if both strings are equal
5        if (firstString.equals(secondString)) {
6            // If both strings are the same, there is no uncommon subsequence
7            return -1;
8        } else {
9            // If the strings are not equal, the LUS is the length of the longer string
10            // because the entire string itself is an uncommon subsequence
11            return Math.max(firstString.length(), secondString.length());
12        }
13    }
14}
15

1class Solution {
2public:
3    int findLUSlength(string strA, string strB) {
4        // If both strings are equal, there will be no uncommon subsequence.
5        if (strA == strB) {
6            return -1;
7        }
8        // If strings are not equal, the longest uncommon subsequence is the length
9        // of the longer string because the two strings can't be subsequences of each other.
10        return max(strA.size(), strB.size());
11    }
12};
13

1// This function finds the length of the Longest Uncommon Subsequence between two strings.
2// If the strings are identical, it returns -1, indicating there is no uncommon subsequence.
3// If the strings are different, it returns the length of the longer string.
4// 
5// Parameters:
6// a - The first string to compare.
7// b - The second string to compare.
8// 
9// Returns:
10// The length of the longest uncommon subsequence, or -1 if no such subsequence exists.
11function findLUSlength(a: string, b: string): number {
12    // Compare the two strings; if they are not equal, return the length of the longer string.
13    // If they are equal, return -1 as there are no uncommon subsequences.
14    return a !== b ? Math.max(a.length, b.length) : -1;
15}
16

Not Sure What to Study? Take the 2-min Quiz：

Which of the following shows the order of node visit in a Breadth-first Search?

I don’t know

Time and Space Complexity

The time complexity of the code is O(1), because it performs a constant number of operations regardless of the input size. It only compares the two strings for equality and then finds the length of the longer string if they are not equal.

The space complexity of the code is also O(1) because it does not allocate any additional space that is dependent on the input size. The space used is for the input strings a and b, which is not counted towards space complexity as it is considered input space, and the space for storing the return value.

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

Which algorithm is best for finding the shortest distance between two points in an unweighted graph?

Depth-First SearchBreadth-First SearchBinary SearchPriority Queue

I don’t know

Overview

Basic Data Structures

Basic Algorithms

Overview

Sorted Array

Implicitly Sorted Array

Advanced

Speedrun

Introduction

DFS on Tree

Binary Search Tree

Advanced

Combinatorial Search

Pruning

Additional States

Aggregation and Memoization

Dedup

Additional Practices

Speedrun

Introduction

BFS on Tree

Introduction

Vanilla BFS

Matrix as Graph

Implicit Graph

Directed Graph / Topological Sort

Weighted Graph

Minimum Spanning Tree

Speedrun

Introduction

Same Direction

Opposite Direction

Sliding Window

Prefix Sum

Cycle Finding

Advanced

Speedrun

Introduction

Top K

Moving Best

Multiple Heaps

Introduction

Grid

Dynamic number of subproblems

Interval

Dual-Sequence

Knapsack

Bitmask

Additional Practices

Disjoint Set Union | Union Find

Trie

Data Structure Design

Segment Tree

Interval

Monotonic Stack

Divide and Conquer

Line Sweep

Tree Traversal without Recursion

Greedy

Math

Matrix

Classics

Concepts

Projects

Amazon OA

Microsoft OA

Google OA

Twitter OA

Editorials

521. Longest Uncommon Subsequence I

Problem Description

Intuition

Solution Approach

Example Walkthrough

Solution Implementation

Time and Space Complexity

Recommended Readings