Longest Uncommon Subsequence II solution and explanation
Google
9 more videos on this problem
Longest Uncommon Subsequence II | Leetcode 522 | Live Coding session 🔥🔥🔥🔥Coding Decoded · 9:45 · 4K views
Longest Uncommon Subsequence II | Strings | 522 LeetCode | Day 27CodeWithSunny · 15:35 · 3K views
Leetcode - Longest Uncommon Subsequence II (Python)Timothy H Chang · 6:52 · 1K views
Longest Uncommon Subsequence II | A Detailed Explanation with DiagramsTanishq Chaudhary · 16:06 · 686 views
Daily Leetcode #514: Aug 27, 2021 - 522. Longest Uncommon Subsequence IIProgramming Live with Larry · 12:25 · 557 views
522. Longest Uncommon Subsequence II /DAILY CHALLENGE5 Minutes Code · 10:26 · 510 views
Leetcode 522: Longest Uncommon Subsequence IIYouScaredMe · 7:53 · 265 views
Longest Uncommon Subsequence IISandeep Vaid · 9:23 · 146 views
Longest Uncommon Subsequence II #LeetCode 26-08-2021Zeel Prajapati · 4:14 · 49 views
Longest Uncommon Subsequence IIThe Whiz · 10:31 · 48 views
The problem
Given an array of strings strs, return the length of the longest uncommon subsequence between them. If the longest uncommon subsequence does not exist, return -1.
An uncommon subsequence between an array of strings is a string that is a subsequence of one string but not the others.
A subsequence of a string s is a string that can be obtained after deleting any number of characters from s.
- For example,
"abc"is a subsequence of"aebdc"because you can delete the underlined characters in"aebdc"to get"abc". Other subsequences of"aebdc"include"aebdc","aeb", and""(empty string).
Example 1:
Input: strs = ["aba","cdc","eae"] Output: 3
Example 2:
Input: strs = ["aaa","aaa","aa"] Output: -1
Constraints:
2 <= strs.length <= 501 <= strs[i].length <= 10strs[i]consists of lowercase English letters.
Approach overview
Problem Overview: You receive an array of strings and must return the length of the longest string that is not a subsequence of any other string in the array. If every string can be formed as a subsequence of another, the answer is -1. The challenge is efficiently verifying subsequence relationships across multiple strings.
Approach 1: Brute Force Check (O(n^2 * L) time, O(1) space)
Check every string against every other string and test whether it appears as a subsequence. For each pair, run a subsequence check using two pointers: move one pointer through the candidate string and another through the potential parent string while matching characters. If a string is not a subsequence of any other string, it is an uncommon subsequence candidate. Track the maximum length among valid candidates.
This method directly models the definition of the problem. With n strings and maximum length L, each subsequence comparison costs O(L), and you perform up to n^2 comparisons. The approach is straightforward and useful for understanding the mechanics of subsequence matching in string problems.
Approach 2: Sorted Length Check (O(n^2 * L) time, O(n) space)
A better strategy is to process longer strings first. Sort the input array in descending order by length using sorting. The first string that is not a subsequence of any other string must be the answer because no later string can be longer.
After sorting, iterate through each string and check whether it is a subsequence of any other string. Use the same two‑pointer subsequence check. A small optimization is handling duplicates with a hash table: if a string appears multiple times, it cannot be uncommon because identical strings are subsequences of each other. Skip those early to reduce unnecessary comparisons.
The key insight is that once you encounter a valid uncommon subsequence while scanning from longest to shortest, you can immediately return its length. This avoids evaluating shorter candidates and reduces practical runtime even though the theoretical complexity remains O(n^2 * L).
Recommended for interviews: The sorted length approach is what most interviewers expect. Starting with brute force shows you understand the definition of subsequences and pairwise comparison. Moving to the sorted strategy demonstrates optimization thinking: process candidates in descending length order and exit early once a valid uncommon subsequence appears.
Approach 1: Brute Force Check
This approach involves iterating through every string in the array and checking if it is a subsequence of any other string. If a string is a subsequence of no other string, we note its length and update our longest uncommon subsequence length.
For a given string, iterating over all other strings and checking if the current string can be a subsequence can be done using a helper function.
def is_subsequence(s, t):
it = iter(t)
return all(c in it for c in s)
def findLUSlength(strs):
max_len = -1
for i, s in enumerate(strs):
is_unique = True
for j, t in enumerate(strs):
if i != j and is_subsequence(s, t):
is_unique = False
break
if is_unique:
max_len = max(max_len, len(s))
return max_lenclass Solution {
private boolean isSubsequence(String s, String t) {
int i = 0, j = 0;
while (i < s.length() && j < t.length()) {
if (s.charAt(i) == t.charAt(j)) i++;
j++;
}
return i == s.length();
}
public int findLUSlength(String[] strs) {
int maxLen = -1;
for (int i = 0; i < strs.length; i++) {
boolean isUnique = true;
for (int j = 0; j < strs.length; j++) {
if (i != j && isSubsequence(strs[i], strs[j])) {
isUnique = false;
break;
}
}
if (isUnique) {
maxLen = Math.max(maxLen, strs[i].length());
}
}
return maxLen;
}
}#include <string>
#include <vector>
bool isSubsequence(const std::string &s, const std::string &t) {
int i = 0, j = 0;
while (i < s.length() && j < t.length()) {
if (s[i] == t[j]) i++;
j++;
}
return i == s.length();
}
int findLUSlength(std::vector<std::string>& strs) {
int maxLen = -1;
for (int i = 0; i < strs.size(); i++) {
bool isUnique = true;
for (int j = 0; j < strs.size(); j++) {
if (i != j && isSubsequence(strs[i], strs[j])) {
isUnique = false;
break;
}
}
if (isUnique) {
maxLen = std::max(maxLen, static_cast<int>(strs[i].length()));
}
}
return maxLen;
}function isSubsequence(s, t) {
let i = 0, j = 0;
while (i < s.length && j < t.length) {
if (s[i] === t[j]) i++;
j++;
}
return i === s.length;
}
function findLUSlength(strs) {
let maxLen = -1;
for (let i = 0; i < strs.length; i++) {
let isUnique = true;
for (let j = 0; j < strs.length; j++) {
if (i !== j && isSubsequence(strs[i], strs[j])) {
isUnique = false;
break;
}
}
if (isUnique) {
maxLen = Math.max(maxLen, strs[i].length);
}
}
return maxLen;
}bool isSubsequence(char* s, char* t) {
int i = 0, j = 0;
while (i < strlen(s) && j < strlen(t)) {
if (s[i] == t[j]) i++;
j++;
}
return i == strlen(s);
}
int findLUSlength(char** strs, int strsSize) {
int maxLen = -1;
for (int i = 0; i < strsSize; i++) {
int j;
for (j = 0; j < strsSize; j++) {
if (i != j && isSubsequence(strs[i], strs[j])) {
break;
}
}
if (j == strsSize) {
maxLen = fmax(maxLen, strlen(strs[i]));
}
}
return maxLen;
}public class Solution {
private bool IsSubsequence(string s, string t) {
int i = 0, j = 0;
while (i < s.Length && j < t.Length) {
if (s[i] == t[j]) i++;
j++;
}
return i == s.Length;
}
public int FindLUSlength(string[] strs) {
int maxLen = -1;
for (int i = 0; i < strs.Length; i++) {
bool isUnique = true;
for (int j = 0; j < strs.Length; j++) {
if (i != j && IsSubsequence(strs[i], strs[j])) {
isUnique = false;
break;
}
}
if (isUnique) {
maxLen = Math.Max(maxLen, strs[i].Length);
}
}
return maxLen;
}
}In this Python solution, the helper function is_subsequence checks if a string is a subsequence. The main function findLUSlength loops through each string, determining if it is unique and not a subsequence, to find the longest uncommon subsequence.
Time Complexity: O(n^2 * l) because we check every string pair. Space Complexity: O(1) as constant extra space is employed.
Approach 2: Sorted Length Check
This approach builds upon sorting the strings based on their length in descending order. The idea is to try longer strings first, as they have a better chance of being unique. The process involves checking if the current string is a subsequence of any other strings.
def is_subsequence(s, t):
it = iter(t)
return all(c in it for c in s)
def findLUSlength(strs):
strs.sort(key=len, reverse=True)
for i, s in enumerate(strs):
is_unique = True
for j, t in enumerate(strs):
if i != j and is_subsequence(s, t):
is_unique = False
break
if is_unique:
return len(s)
return -1import java.util.Arrays;
class Solution {
private boolean isSubsequence(String s, String t) {
int i = 0, j = 0;
while (i < s.length() && j < t.length()) {
if (s.charAt(i) == t.charAt(j)) i++;
j++;
}
return i == s.length();
}
public int findLUSlength(String[] strs) {
Arrays.sort(strs, (a, b) -> b.length() - a.length());
for (int i = 0; i < strs.length; i++) {
boolean isUnique = true;
for (int j = 0; j < strs.length; j++) {
if (i != j && isSubsequence(strs[i], strs[j])) {
isUnique = false;
break;
}
}
if (isUnique) {
return strs[i].length();
}
}
return -1;
}
}#include <string>
#include <vector>
#include <algorithm>
bool isSubsequence(const std::string &s, const std::string &t) {
int i = 0, j = 0;
while (i < s.length() && j < t.length()) {
if (s[i] == t[j]) i++;
j++;
}
return i == s.length();
}
int findLUSlength(std::vector<std::string>& strs) {
std::sort(strs.begin(), strs.end(), [](const std::string& a, const std::string& b) {
return a.length() > b.length();
});
for (int i = 0; i < strs.size(); i++) {
bool isUnique = true;
for (int j = 0; j < strs.size(); j++) {
if (i != j && isSubsequence(strs[i], strs[j])) {
isUnique = false;
break;
}
}
if (isUnique) {
return strs[i].length();
}
}
return -1;
}function isSubsequence(s, t) {
let i = 0, j = 0;
while (i < s.length && j < t.length) {
if (s[i] === t[j]) i++;
j++;
}
return i === s.length;
}
function findLUSlength(strs) {
strs.sort((a, b) => b.length - a.length);
for (let i = 0; i < strs.length; i++) {
let isUnique = true;
for (let j = 0; j < strs.length; j++) {
if (i !== j && isSubsequence(strs[i], strs[j])) {
isUnique = false;
break;
}
}
if (isUnique) {
return strs[i].length;
}
}
return -1;
}bool isSubsequence(char* s, char* t) {
int i = 0, j = 0;
while (i < strlen(s) && j < strlen(t)) {
if (s[i] == t[j]) i++;
j++;
}
return i == strlen(s);
}
int compare(const void* a, const void* b) {
return strlen(*(const char**)b) - strlen(*(const char**)a);
}
int findLUSlength(char** strs, int strsSize) {
qsort(strs, strsSize, sizeof(char*), compare);
int maxLen = -1;
for (int i = 0; i < strsSize; i++) {
int j;
for (j = 0; j < strsSize; j++) {
if (i != j && isSubsequence(strs[i], strs[j])) {
break;
}
}
if (j == strsSize) {
return strlen(strs[i]);
}
}
return -1;
}using System;
using System.Linq;
public class Solution {
private bool IsSubsequence(string s, string t) {
int i = 0, j = 0;
while (i < s.Length && j < t.Length) {
if (s[i] == t[j]) i++;
j++;
}
return i == s.Length;
}
public int FindLUSlength(string[] strs) {
Array.Sort(strs, (a, b) => b.Length.CompareTo(a.Length));
for (int i = 0; i < strs.Length; i++) {
bool isUnique = true;
for (int j = 0; j < strs.Length; j++) {
if (i != j && IsSubsequence(strs[i], strs[j])) {
isUnique = false;
break;
}
}
if (isUnique) {
return strs[i].Length;
}
}
return -1;
}
}This Python solution sorts the strings based on their length in descending order. It checks each one to determine if it is not a subsequence of any other. If such a string is found, its length is returned.
Time Complexity: O(n^2 * l) with the addition of O(n log n) for sorting. Space Complexity: O(1) due to limited additional storage needs.
Approach 3: Subsequence Judgment
We define a function check(s, t) to determine whether string s is a subsequence of string t. We can use a two-pointer approach, initializing two pointers i and j to point to the beginning of strings s and t respectively, then continuously move pointer j. If s[i] equals t[j], then move pointer i. Finally, check if i equals the length of s. If i equals the length of s, it means s is a subsequence of t.
To determine if string s is unique, we only need to take string s itself and compare it with other strings in the list. If there exists a string for which s is a subsequence, then s is not unique. Otherwise, string s is unique. We take the longest string among all unique strings.
The time complexity is O(n^2 times m), where n is the length of the list of strings, and m is the average length of the strings. The space complexity is O(1).
function findLUSlength(strs: string[]): number {
const n = strs.length;
let ans = -1;
const check = (s: string, t: string): boolean => {
const [m, n] = [s.length, t.length];
let i = 0;
for (let j = 0; i < m && j < n; ++j) {
if (s[i] === t[j]) {
++i;
}
}
return i === m;
};
for (let i = 0; i < n; ++i) {
let x = strs[i].length;
for (let j = 0; j < n; ++j) {
if (i !== j && check(strs[i], strs[j])) {
x = -1;
break;
}
}
ans = Math.max(ans, x);
}
return ans;
}func findLUSlength(strs []string) int {
ans := -1
check := func(s, t string) bool {
m, n := len(s), len(t)
i := 0
for j := 0; i < m && j < n; j++ {
if s[i] == t[j] {
i++
}
}
return i == m
}
for i, s := range strs {
x := len(s)
for j, t := range strs {
if i != j && check(s, t) {
x = -1
break
}
}
ans = max(ans, x)
}
return ans
}Complexity comparison
| Approach | Complexity |
|---|---|
| Brute Force Check | Time Complexity: O(n^2 * l) because we check every string pair. Space Complexity: O(1) as constant extra space is employed. |
| Sorted Length Check | Time Complexity: O(n^2 * l) with the addition of O(n log n) for sorting. Space Complexity: O(1) due to limited additional storage needs. |
| Subsequence Judgment | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Check | O(n^2 * L) | O(1) | When implementing the simplest interpretation of the problem or during initial reasoning in interviews |
| Sorted Length Check | O(n^2 * L) | O(n) | General optimized approach; process longest strings first and exit early when a valid uncommon subsequence is found |
Frequently asked questions
Is Longest Uncommon Subsequence II easy or hard?
Longest Uncommon Subsequence II is considered a medium‑difficulty problem. The logic for checking subsequences is simple, but the challenge comes from handling comparisons across many strings efficiently and recognizing that sorting by length allows early termination.
How to solve Longest Uncommon Subsequence II in O(n)?
An O(n) solution is not feasible because the algorithm must compare strings to determine subsequence relationships. Each comparison requires scanning characters, and multiple pairwise checks are required. The practical optimal approach remains O(n^2 * L) using sorting and efficient subsequence checks.
What is the best approach for Longest Uncommon Subsequence II?
The sorted length check approach is typically the best solution. Sort all strings by length in descending order, then check whether each string is a subsequence of any other string using a two‑pointer comparison. The first string that is not a subsequence of another is the answer. This runs in O(n^2 * L) time where L is the maximum string length.
What data structure is used in Longest Uncommon Subsequence II?
The solution mainly relies on arrays of strings and simple subsequence checks using two pointers. A hash table can be used to count duplicate strings and skip them early. Sorting is also used in the optimized approach to process longer strings first.
What is the time complexity of Longest Uncommon Subsequence II?
The common solution runs in O(n^2 * L) time. You may need to compare each string against every other string, and each subsequence check takes O(L) using a two‑pointer scan. Space complexity ranges from O(1) to O(n) depending on whether a hash table is used to track duplicate strings.
Longest Uncommon Subsequence II Python or Java solution approach?
Both Python and Java implementations typically sort the array of strings by length in descending order and then perform subsequence checks. A helper function uses two pointers to verify whether one string is a subsequence of another. The algorithm runs in O(n^2 * L) time and works well within the typical constraints.
Is Longest Uncommon Subsequence II asked at Google, Amazon, or Meta?
Problems involving subsequences, string comparison, and candidate filtering appear frequently in interviews at large tech companies such as Amazon, Google, and Meta. While this exact problem may not appear verbatim, the techniques used—two‑pointer subsequence checks, sorting by length, and duplicate filtering—are common interview patterns.