Longest Uncommon Subsequence II — Problem & Solution
Longest Uncommon Subsequence II solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Longest Uncommon Subsequence II is a medium coding problem on arrays, strings and hash table, asked in Google interviews.
- Difficulty: Medium
- Topics: Arrays, Strings, Hash Table, Sorting, Two Pointers
- Asked at: 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 an array of strings strs, return the length of the longest uncommon subsequence among them, or -1 if none exists.
An uncommon subsequence is a string that is a subsequence of one string of the array but not a subsequence of any of the others. A subsequence is obtained by deleting any number of characters (possibly none) without reordering the rest. Equal strings at two different positions count as two different strings.
Example 1
Input: strs = ["aba","cdc","eae"]
Output: 3
Explanation: Each whole string is a subsequence of no other string.
Example 2
Input: strs = ["code","kairo","kairo","co"]
Output: 4
Explanation: `"code"` is not a subsequence of `"kairo"` or `"co"`; each `"kairo"` is a subsequence of the other one.
Example 3
Input: strs = ["aaa","aaa","aa"]
Output: -1
Constraints
2 <= strs.length <= 501 <= strs[i].length <= 10strs[i] consists of lowercase English letters
Hints for Longest Uncommon Subsequence II
Hint 1
If some subsequence
xofstrs[i]is uncommon, thenstrs[i]itself is uncommon too — any string containingstrs[i]as a subsequence would containxas well.Hint 2
So only the whole strings are candidates: check each one against all the others.
Hint 3
A two-pointer scan tells whether
sis a subsequence oftinO(|t|). Return the longest candidate that is a subsequence of no other string.
How to solve Longest Uncommon Subsequence II
The answer, if it exists, is the length of a whole input string: extending an uncommon subsequence of strs[i] to all of strs[i] keeps it uncommon and only makes it longer.
Approach
- For every index
i, checkstrs[i]against everystrs[j]withj != iusing a two-pointer subsequence test. - If
strs[i]is a subsequence of none of them, it is uncommon: update the answer with its length. - Return the best length found, or
-1.
Why it works
Suppose x is an uncommon subsequence of strs[i]. If strs[i] were a subsequence of some other strs[j], then x (a subsequence of strs[i]) would also be a subsequence of strs[j] — a contradiction. So strs[i] is uncommon and at least as long as x; checking whole strings loses nothing.
Complexity
- Time —
O(n^2 · L) fornstrings of length up toL`` - Space —
O(1)
Pitfalls
- A duplicated string is a subsequence of its copy, so neither copy counts.
- Compare by index, not by value — skip only
j == i, not every equal string. - Return
-1, not0, when nothing qualifies.
Reference solution
Python
from typing import List
def findLUSlength(strs: List[str]) -> int:
def is_sub(s, t):
i = 0
for ch in t:
if i < len(s) and s[i] == ch:
i += 1
return i == len(s)
best = -1
for i, s in enumerate(strs):
if len(s) <= best:
continue
if all(j == i or not is_sub(s, t) for j, t in enumerate(strs)):
best = len(s)
return bestJava
static boolean lusIsSub(String s, String t) {
int i = 0;
for (int j = 0; j < t.length() && i < s.length(); j++) if (s.charAt(i) == t.charAt(j)) i++;
return i == s.length();
}
public static int findLUSlength(String[] strs) {
int best = -1;
for (int i = 0; i < strs.length; i++) {
if (strs[i].length() <= best) continue;
boolean ok = true;
for (int j = 0; j < strs.length && ok; j++) if (j != i && lusIsSub(strs[i], strs[j])) ok = false;
if (ok) best = strs[i].length();
}
return best;
}C++
static bool lusIsSub(const string& s, const string& t) {
size_t i = 0;
for (size_t j = 0; j < t.size() && i < s.size(); j++) if (s[i] == t[j]) i++;
return i == s.size();
}
int findLUSlength(vector<string>& strs) {
int best = -1;
for (size_t i = 0; i < strs.size(); i++) {
if ((int) strs[i].size() <= best) continue;
bool ok = true;
for (size_t j = 0; j < strs.size() && ok; j++) if (j != i && lusIsSub(strs[i], strs[j])) ok = false;
if (ok) best = (int) strs[i].size();
}
return best;
}JavaScript
var findLUSlength = function(strs) {
var isSub = function(s, t) {
var i = 0;
for (var j = 0; j < t.length && i < s.length; j++) if (s[i] === t[j]) i++;
return i === s.length;
};
var best = -1;
for (var i = 0; i < strs.length; i++) {
if (strs[i].length <= best) continue;
var ok = true;
for (var j = 0; j < strs.length && ok; j++) if (j !== i && isSub(strs[i], strs[j])) ok = false;
if (ok) best = strs[i].length;
}
return best;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.