522

522. Longest Uncommon Subsequence II (Medium)

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:

• 1 <= strs.length <= 50
• 1 <= strs[i].length <= 10
• strs[i] consists of lowercase English letters.

Companies:
Google

Related Topics:
Array, Hash Table, Two Pointers, String, Sorting

Similar Questions:

• Longest Uncommon Subsequence I (Easy)

Solution 1.

The answer must be one of the strings in A. We can prove by contradiction. Assume the longest LUS is a subsequence of A[i] but not A[i] itself, we can always add the rest characters in A[i] to get a longer LUS which contradicts with the assumption.

So, we can iterate through the strings in A and check if it's a subsequence of another string of longer or equal length. If it's not, then it's the LUS.

// OJ: https://leetcode.com/problems/longest-uncommon-subsequence-ii/
// Author: github.com/lzl124631x
// Time: O(N^2 * W) where `N` is the number of elements in `A` and `W` is the maximum length of a string in `A`.
// Space: O(1)
class Solution {
    bool isSubsequence(string &a, string &b) {
        int i = 0, j = 0, M = a.size(), N = b.size();
        for (; i < M && j < N; ) {
            while (j < N && a[i] != b[j]) ++j;
            if (j < N && a[i] == b[j]) ++i, ++j;
        }
        return i == M;
    }
public:
    int findLUSlength(vector<string>& A) {
        sort(begin(A), end(A), [](auto &a, auto &b) { return a.size() > b.size(); });
        for (int i = 0; i < A.size(); ++i) {
            bool good = true;
            for (int j = 0; j < A.size() && A[i].size() <= A[j].size() && good; ++j) {
                if (i != j && isSubsequence(A[i], A[j])) good = false;
            }
            if (good) return A[i].size();
        }
        return -1;
    }
};