Longest Uncommon Subsequence II

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

1
2


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

Example 2

1
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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20


class Solution {
public:
    bool isSubseq(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 ans = -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 (isSubseq(strs[i], strs[j])) { uncommon = false; break; }
            }
            if (uncommon) ans = max(ans, (int)strs[i].size());
        }
        return ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29


func isSubseq(a, b string) bool {
    i := 0
    for j := 0; j < len(b); j++ {
        if i < len(a) && a[i] == b[j] {
            i++
        }
    }
    return i == len(a)
}
func findLUSlength(strs []string) int {
    ans := -1
    n := len(strs)
    for i := 0; i < n; i++ {
        uncommon := true
        for j := 0; j < n; j++ {
            if i == j {
                continue
            }
            if isSubseq(strs[i], strs[j]) {
                uncommon = false
                break
            }
        }
        if uncommon && len(strs[i]) > ans {
            ans = len(strs[i])
        }
    }
    return ans
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19


class Solution {
    boolean isSubseq(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 ans = -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 (isSubseq(strs[i], strs[j])) { uncommon = false; break; }
            }
            if (uncommon) ans = Math.max(ans, strs[i].length());
        }
        return ans;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19


class Solution {
    fun isSubseq(a: String, b: String): Boolean {
        var i = 0
        for (c in b) if (i < a.length && a[i] == c) i++
        return i == a.length
    }
    fun findLUSlength(strs: Array<String>): Int {
        var ans = -1
        for (i in strs.indices) {
            var uncommon = true
            for (j in strs.indices) {
                if (i == j) continue
                if (isSubseq(strs[i], strs[j])) { uncommon = false; break }
            }
            if (uncommon) ans = maxOf(ans, strs[i].length)
        }
        return ans
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21


class Solution:
    def isSubseq(self, a: str, b: str) -> bool:
        i = 0
        for c in b:
            if i < len(a) and a[i] == c:
                i += 1
        return i == len(a)
    def findLUSlength(self, strs: list[str]) -> int:
        ans = -1
        n = len(strs)
        for i in range(n):
            uncommon = True
            for j in range(n):
                if i == j:
                    continue
                if self.isSubseq(strs[i], strs[j]):
                    uncommon = False
                    break
            if uncommon:
                ans = max(ans, len(strs[i]))
        return ans

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24


impl Solution {
    pub fn find_lus_length(strs: Vec<String>) -> i32 {
        fn is_subseq(a: &str, b: &str) -> bool {
            let (mut i, a_bytes) = (0, a.as_bytes());
            for &c in b.as_bytes() {
                if i < a_bytes.len() && a_bytes[i] == c { i += 1; }
            }
            i == a_bytes.len()
        }
        let n = strs.len();
        let mut ans = -1;
        for i in 0..n {
            let mut uncommon = true;
            for j in 0..n {
                if i == j { continue; }
                if is_subseq(&strs[i], &strs[j]) { uncommon = false; break; }
            }
            if uncommon {
                ans = ans.max(strs[i].len() as i32);
            }
        }
        ans
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19


class Solution {
    isSubseq(a: string, b: string): boolean {
        let i = 0;
        for (const c of b) if (i < a.length && a[i] === c) i++;
        return i === a.length;
    }
    findLUSlength(strs: string[]): number {
        let ans = -1;
        for (let i = 0; i < strs.length; ++i) {
            let uncommon = true;
            for (let j = 0; j < strs.length; ++j) {
                if (i === j) continue;
                if (this.isSubseq(strs[i], strs[j])) { uncommon = false; break; }
            }
            if (uncommon) ans = Math.max(ans, strs[i].length);
        }
        return ans;
    }
}

Complexity

⏰ Time complexity: O(n^2 * m), where n is the number of strings and m is the average string length, as we check each string against all others.
🧺 Space complexity: O(1), as we use only a few variables.

Problem#

Examples#

Example 1#

Example 2#

Constraints#

Solution#

Method 1 – Brute Force with Subsequence Check#

Intuition#

Approach#

Code#

Complexity#