"static/chunks/874-64ff3adb125f84b1.js","269","static/chunks/269-5f9235f83b944543.js","222","static/chunks/222-e37d1f81e0d6d2ef.js","934","static/chunks/app/cs/problems/%5Bslug%5D/page-935d3f20891d8cfc.js"],"default"] 18:I[4821,["874","static/chunks/874-64ff3adb125f84b1.js","269","static/chunks/269-5f9235f83b944543.js","222","static/chunks/222-e37d1f81e0d6d2ef.js","934","static/chunks/app/cs/problems/%5Bslug%5D/page-935d3f20891d8cfc.js"],"default"] 19:I[2647,["874","static/chunks/874-64ff3adb125f84b1.js","269","static/chunks/269-5f9235f83b944543.js","222","static/chunks/222-e37d1f81e0d6d2ef.js","934","static/chunks/app/cs/problems/%5Bslug%5D/page-935d3f20891d8cfc.js"],"default"] 1b:I[7912,["874","static/chunks/874-64ff3adb125f84b1.js","269","static/chunks/269-5f9235f83b944543.js","222","static/chunks/222-e37d1f81e0d6d2ef.js","934","static/chunks/app/cs/problems/%5Bslug%5D/page-935d3f20891d8cfc.js"],"default"] 1a:T1d15,

Problem

Given an array of strings strs, return the length of thelongest 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 "a _e_ b _d_ c" to get "abc". Other subsequences of "aebdc" include "aebdc", "aeb", and "" (empty string).

Examples

Example 1

Input: strs = ["aba","cdc","eae"]
Output: 3

Example 2

Input: strs = ["aaa","aaa","aa"]
Output: -1

Constraints

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

Solution

Method 1 – Brute Force with Subsequence Check

Intuition

The longest uncommon subsequence must be one of the input strings. For each string, if it is not a subsequence of any other string, it is a candidate. We check all strings and return the length of the longest such string.

Approach

For each string in the array, check if it is a subsequence of any other string (except itself).
If not, update the answer with its length.
Return the maximum length found, or -1 if none exists.
Use a helper function to check if one string is a subsequence of another.

Code

[{"language":"C++","code":"class Solution {\npublic:\n    bool isSubseq(const string& a, const string& b) {\n        int i = 0;\n        for (char c : b) if (i < a.size() && a[i] == c) ++i;\n        return i == a.size();\n    }\n    int findLUSlength(vector<string>& strs) {\n        int ans = -1, n = strs.size();\n        for (int i = 0; i < n; ++i) {\n            bool uncommon = true;\n            for (int j = 0; j < n; ++j) {\n                if (i == j) continue;\n                if (isSubseq(strs[i], strs[j])) { uncommon = false; break; }\n            }\n            if (uncommon) ans = max(ans, (int)strs[i].size());\n        }\n        return ans;\n    }\n};","lang":"cpp"},{"language":"Go","code":"func isSubseq(a, b string) bool {\n    i := 0\n    for j := 0; j < len(b); j++ {\n        if i < len(a) && a[i] == b[j] {\n            i++\n        }\n    }\n    return i == len(a)\n}\nfunc findLUSlength(strs []string) int {\n    ans := -1\n    n := len(strs)\n    for i := 0; i < n; i++ {\n        uncommon := true\n        for j := 0; j &#

Related Tags