Problem Description

The Longest Uncommon Subsequence II problem asks you to find the length of the longest uncommon subsequence among a list of strings.

• You are given an array of strings strs.
• An uncommon subsequence is a string that is a subsequence of one string in the list, but not a subsequence of any other string in the list.
• Your task is to return the length of the longest such uncommon subsequence. If no such subsequence exists, return -1.

Definitions:

• A subsequence of a string is a new string generated from the original string with some characters (can be none) deleted without changing the relative order of the remaining characters.
• For example, "abc" is a subsequence of "aebdc".

Constraints:

• 1 ≤ strs.length ≤ 50
• 1 ≤ strs[i].length ≤ 10
• strs[i] consists only of lowercase English letters.

Thought Process

The problem asks us to find the longest string that is a subsequence of one string in the list, but not a subsequence of any other string. The naive approach is to check all possible subsequences of all strings, but this quickly becomes infeasible due to the exponential number of subsequences.

However, we can notice that any string itself is a subsequence of itself. So, if a string is not a subsequence of any other string in the list (except possibly itself), then it is a valid uncommon subsequence candidate.

With this in mind, instead of generating all possible subsequences, we can simply check for each string in the list whether it is a subsequence of any other string. If not, it's a candidate, and we track the length of the longest such string.

To optimize, we can process the strings in order of decreasing length, so that if we find a longer uncommon subsequence, we don't need to check shorter ones.

Solution Approach

• Step 1: Sort the input array strs in order of decreasing string length. This ensures we check longer strings first, maximizing our chance to find the answer early.
• Step 2: For each string s in strs:
  • For each other string t in strs (skip if s and t are at the same index), check if s is a subsequence of t.
  • If s is not a subsequence of any other string, then s is an uncommon subsequence.
• Step 3: Among all such uncommon subsequences, keep track of the maximum length found.
• Step 4: If no uncommon subsequence is found, return -1. Otherwise, return the length of the longest one.

Why this works: Since the maximum length of a string is 10 and the number of strings is at most 50, checking if a string is a subsequence of another is efficient. We use a helper function to check if one string is a subsequence of another using two pointers.

Example Walkthrough

Let's use the example strs = ["aba", "cdc", "eae"].

• Sort the strings by length (all are length 3).
• For each string, check if it is a subsequence of any other string:
• "aba":
  • Is "aba" a subsequence of "cdc"? No.
  • Is "aba" a subsequence of "eae"? No.
  • So, "aba" is uncommon.
• "cdc":
  • Is "cdc" a subsequence of "aba"? No.
  • Is "cdc" a subsequence of "eae"? No.
  • So, "cdc" is uncommon.
• "eae":
  • Is "eae" a subsequence of "aba"? No.
  • Is "eae" a subsequence of "cdc"? No.
  • So, "eae" is uncommon.
• All three strings are uncommon subsequences. The maximum length is 3, so we return 3.

Time and Space Complexity

• Brute-force approach: Generating all possible subsequences of all strings is exponential (O(2^L) per string), which is infeasible.
• Optimized approach:
  • For each string, we compare it to all other strings (O(N^2) comparisons, N ≤ 50).
  • Each subsequence check is O(L), where L ≤ 10.
  • Total time complexity: O(N^2 * L), which is acceptable for the constraints.
  • Space complexity: O(1) extra (ignoring input), as we only use pointers and a few variables.

Summary

The key insight is that the only candidates for the longest uncommon subsequence are the original strings themselves. By checking, for each string, whether it is a subsequence of any other string, we can efficiently determine the answer. Sorting by length lets us return early with the longest answer. This approach avoids brute-force enumeration of all subsequences and leverages the small input size for an efficient solution.

Code Implementation

class Solution:
    def findLUSlength(self, strs):
        def is_subsequence(a, b):
            i = 0
            for c in b:
                if i < len(a) and a[i] == c:
                    i += 1
            return i == len(a)

        max_len = -1
        n = len(strs)
        for i, s in enumerate(strs):
            if all(i == j or not is_subsequence(s, strs[j]) for j in range(n)):
                max_len = max(max_len, len(s))
        return max_len
      

class Solution {
public:
    bool isSubsequence(const string& a, const string& b) {
        int i = 0;
        for (char c : b) {
            if (i < a.size() && a[i] == c) ++i;
        }
        return i == a.size();
    }

    int findLUSlength(vector<string>& strs) {
        int maxLen = -1, n = strs.size();
        for (int i = 0; i < n; ++i) {
            bool uncommon = true;
            for (int j = 0; j < n; ++j) {
                if (i == j) continue;
                if (isSubsequence(strs[i], strs[j])) {
                    uncommon = false;
                    break;
                }
            }
            if (uncommon) maxLen = max(maxLen, (int)strs[i].size());
        }
        return maxLen;
    }
};
      

class Solution {
    private boolean isSubsequence(String a, String b) {
        int i = 0;
        for (char c : b.toCharArray()) {
            if (i < a.length() && a.charAt(i) == c) i++;
        }
        return i == a.length();
    }

    public int findLUSlength(String[] strs) {
        int maxLen = -1, n = strs.length;
        for (int i = 0; i < n; i++) {
            boolean uncommon = true;
            for (int j = 0; j < n; j++) {
                if (i == j) continue;
                if (isSubsequence(strs[i], strs[j])) {
                    uncommon = false;
                    break;
                }
            }
            if (uncommon) maxLen = Math.max(maxLen, strs[i].length());
        }
        return maxLen;
    }
}
      

var findLUSlength = function(strs) {
    function isSubsequence(a, b) {
        let i = 0;
        for (let c of b) {
            if (i < a.length && a[i] === c) i++;
        }
        return i === a.length;
    }
    let maxLen = -1, n = strs.length;
    for (let i = 0; i < n; i++) {
        let uncommon = true;
        for (let j = 0; j < n; j++) {
            if (i === j) continue;
            if (isSubsequence(strs[i], strs[j])) {
                uncommon = false;
                break;
            }
        }
        if (uncommon) maxLen = Math.max(maxLen, strs[i].length);
    }
    return maxLen;
};