Longest Uncommon Subsequence Ii - Leetcode Solution

Problem statement:

Given a list of strings, find the length of the longest uncommon subsequence among them. A subsequence is a sequence that can be derived from one sequence by deleting some characters without changing the order of the remaining elements. The length of a subsequence is the number of elements left after deletion.

If there are no uncommon subsequences, return -1.

Example:

Input: ["aba", "cdc", "eae"] Output: 3

Explanation: The longest uncommon subsequence is "eae", because it is not a subsequence of the other strings.

Solution:

To solve this problem, we can start by sorting the list of strings in decreasing order of length. This is because the longest uncommon subsequence will be present in the longest string in the list.

We can then iterate through the list of strings, and check each string against all other longer strings in the list. If the current string is not a subsequence of any of the longer strings, we can return its length as the answer.

If we reach the end of the list without finding any such string, we can return -1.

Here is the Python code for the solution:

def is_subsequence(s, t): i, j = 0, 0 while i < len(s) and j < len(t): if s[i] == t[j]: i += 1 j += 1 return i == len(s)

def find_lus_length(strs): strs.sort(key=len, reverse=True) for i, s in enumerate(strs): if all(is_subsequence(s, strs[j]) for j in range(len(strs)) if j != i): return len(s) return -1

In the above code, the function is_subsequence checks whether the string s is a subsequence of the string t. The function find_lus_length sorts the list of strings and checks each string against all other longer strings.

This code has a time complexity of O(n^2 * m), where n is the number of strings and m is the maximum length of the strings. This is because we are iterating through all pairs of strings and checking whether one string is a subsequence of the other.

However, we can improve the performance of the code by optimizing the is_subsequence function. We can use a two-pointer approach to check whether s is a subsequence of t in linear time. Here is the optimized code:

def is_subsequence(s, t): i, j = 0, 0 while i < len(s) and j < len(t): if s[i] == t[j]: i += 1 j += 1 return i == len(s)

def find_lus_length(strs): strs.sort(key=len, reverse=True) for i, s in enumerate(strs): if all(not is_subsequence(s, strs[j]) for j in range(i+1, len(strs))): return len(s) return -1

In this code, the is_subsequence function returns True if s is not a subsequence of t. The find_lus_length function now iterates through all strings after the current string and checks whether s is not a subsequence of any of them. This code has a time complexity of O(n^2), which is much faster than the previous code.

1