Longest Uncommon Subsequence II

medium array hash map two pointers string sorting

Problem

Find the length of the longest string that is a subsequence of one string in strs and not a subsequence of any other. Return −1 if none.

Inputstrs = ["aba","cdc","eae"]

Output3

Sort by len desc; for each, check it isn't a subsequence of any other.

strings (comma-separated)

def find_lus_length(strs):
    def is_sub(a, b):
        i = 0
        for c in b:
            if i < len(a) and a[i] == c: i += 1
        return i == len(a)
    strs.sort(key=lambda s: -len(s))
    for i, s in enumerate(strs):
        if all(not is_sub(s, strs[j]) for j in range(len(strs)) if j != i):
            return len(s)
    return -1

function findLUSlength(strs) {
  function isSub(a, b) {
    let i = 0;
    for (const c of b) if (i < a.length && a[i] === c) i++;
    return i === a.length;
  }
  strs.sort((a, b) => b.length - a.length);
  for (let i = 0; i < strs.length; i++) {
    let unique = true;
    for (let j = 0; j < strs.length; j++) {
      if (i !== j && isSub(strs[i], strs[j])) { unique = false; break; }
    }
    if (unique) return strs[i].length;
  }
  return -1;
}

class Solution {
    public int findLUSlength(String[] strs) {
        Arrays.sort(strs, (a, b) -> b.length() - a.length());
        for (int i = 0; i < strs.length; i++) {
            boolean unique = true;
            for (int j = 0; j < strs.length && unique; j++)
                if (i != j && isSub(strs[i], strs[j])) unique = false;
            if (unique) return strs[i].length();
        }
        return -1;
    }
    boolean isSub(String a, String b) {
        int i = 0;
        for (int k = 0; k < b.length() && i < a.length(); k++)
            if (a.charAt(i) == b.charAt(k)) i++;
        return i == a.length();
    }
}

bool isSub(string& a, string& b) {
    int i = 0;
    for (char c : b) if (i < (int)a.size() && a[i] == c) i++;
    return i == (int)a.size();
}
int findLUSlength(vector& strs) {
    sort(strs.begin(), strs.end(), [](auto& a, auto& b){ return a.size() > b.size(); });
    for (int i = 0; i < (int)strs.size(); i++) {
        bool unique = true;
        for (int j = 0; j < (int)strs.size() && unique; j++)
            if (i != j && isSub(strs[i], strs[j])) unique = false;
        if (unique) return strs[i].size();
    }
    return -1;
}

Explanation

The key insight is that the best candidate is always a whole string, never some smaller piece of it. If a full string isn't a subsequence of any other, then it is uncommon; if it is a subsequence of some other, then so is every piece of it, so it gives us nothing.

So we only ever need to test each complete string. We sort the strings by length, longest first, so the first valid one we find is automatically the longest possible answer.

The helper is_sub(a, b) checks whether a is a subsequence of b with a two-pointer walk: scan through b, and each time its character matches the next needed character of a, advance in a. If we consume all of a, it fits inside b.

For each string s, we check it against every other string. If s is not a subsequence of any of them, we return len(s). If no string survives this test, we return -1.

Example: ["aba","cdc","eae"]. None of these length-3 strings is a subsequence of the others, so the first one checked, "aba", already wins with length 3.

Time: O(n² · L) Space: O(1)