Longest Uncommon Subsequence II

Medium
1743.

Longest Uncommon Subsequence II

Longest Uncommon Subsequence II is a medium coding problem on arrays, strings and hash table, asked in Google interviews.

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 <= 50
  • 1 <= strs[i].length <= 10
  • strs[i] consists 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[]} strs
 * @return {number}
 */
var findLUSlength = function(strs) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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.

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 <= 50
  • 1 <= strs[i].length <= 10
  • strs[i] consists of lowercase English letters

Hints for Longest Uncommon Subsequence II

  1. Hint 1

    If some subsequence x of strs[i] is uncommon, then strs[i] itself is uncommon too — any string containing strs[i] as a subsequence would contain x as well.

  2. Hint 2

    So only the whole strings are candidates: check each one against all the others.

  3. Hint 3

    A two-pointer scan tells whether s is a subsequence of t in O(|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

  1. For every index i, check strs[i] against every strs[j] with j != i using a two-pointer subsequence test.
  2. If strs[i] is a subsequence of none of them, it is uncommon: update the answer with its length.
  3. 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) for n strings of length up to L``
  • 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, not 0, 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 best

Java

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.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Strings