522. Longest Uncommon Subsequence II

DifficultyMedium

Description

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:

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

Solutions

Solution 1: Subsequence Judgment

Thinking

With many strings, a longer string may still be a subsequence of another, so length alone is not enough. \(n \le 50\) and short strings make it feasible to test each string against the others.

A two-pointer scan checks whether \(s\) is a subsequence of \(t\). If \(s\) is not a subsequence of any other string, it is uncommon and its length updates the answer. If none survive, return \(-1\).

We define a function \(check(s, t)\) to determine whether string \(s\) is a subsequence of string \(t\). We can use a two-pointer approach, initializing two pointers \(i\) and \(j\) to point to the beginning of strings \(s\) and \(t\) respectively, then continuously move pointer \(j\). If \(s[i]\) equals \(t[j]\), then move pointer \(i\). Finally, check if \(i\) equals the length of \(s\). If \(i\) equals the length of \(s\), it means \(s\) is a subsequence of \(t\).

To determine if string \(s\) is unique, we only need to take string \(s\) itself and compare it with other strings in the list. If there exists a string for which \(s\) is a subsequence, then \(s\) is not unique. Otherwise, string \(s\) is unique. We take the longest string among all unique strings.

The time complexity is \(O(n^2 \times m)\), where \(n\) is the length of the list of strings, and \(m\) is the average length of the strings. The space complexity is \(O(1)\).

Python3JavaC++GoTypeScript

class Solution:
    def findLUSlength(self, strs: List[str]) -> int:
        def check(s: str, t: str):
            i = j = 0
            while i < len(s) and j < len(t):
                if s[i] == t[j]:
                    i += 1
                j += 1
            return i == len(s)

        ans = -1
        for i, s in enumerate(strs):
            for j, t in enumerate(strs):
                if i != j and check(s, t):
                    break
            else:
                ans = max(ans, len(s))
        return ans

class Solution {
    public int findLUSlength(String[] strs) {
        int ans = -1;
        int n = strs.length;
        for (int i = 0, j; i < n; ++i) {
            int x = strs[i].length();
            for (j = 0; j < n; ++j) {
                if (i != j && check(strs[i], strs[j])) {
                    x = -1;
                    break;
                }
            }
            ans = Math.max(ans, x);
        }
        return ans;
    }

    private boolean check(String s, String t) {
        int m = s.length(), n = t.length();
        int i = 0;
        for (int j = 0; i < m && j < n; ++j) {
            if (s.charAt(i) == t.charAt(j)) {
                ++i;
            }
        }
        return i == m;
    }
}

class Solution {
public:
    int findLUSlength(vector<string>& strs) {
        int ans = -1;
        int n = strs.size();
        auto check = [&](const string& s, const string& t) {
            int m = s.size(), n = t.size();
            int i = 0;
            for (int j = 0; i < m && j < n; ++j) {
                if (s[i] == t[j]) {
                    ++i;
                }
            }
            return i == m;
        };
        for (int i = 0, j; i < n; ++i) {
            int x = strs[i].size();
            for (j = 0; j < n; ++j) {
                if (i != j && check(strs[i], strs[j])) {
                    x = -1;
                    break;
                }
            }
            ans = max(ans, x);
        }
        return ans;
    }
};

func findLUSlength(strs []string) int {
    ans := -1
    check := func(s, t string) bool {
        m, n := len(s), len(t)
        i := 0
        for j := 0; i < m && j < n; j++ {
            if s[i] == t[j] {
                i++
            }
        }
        return i == m
    }
    for i, s := range strs {
        x := len(s)
        for j, t := range strs {
            if i != j && check(s, t) {
                x = -1
                break
            }
        }
        ans = max(ans, x)
    }
    return ans
}

function findLUSlength(strs: string[]): number {
    const n = strs.length;
    let ans = -1;
    const check = (s: string, t: string): boolean => {
        const [m, n] = [s.length, t.length];
        let i = 0;
        for (let j = 0; i < m && j < n; ++j) {
            if (s[i] === t[j]) {
                ++i;
            }
        }
        return i === m;
    };
    for (let i = 0; i < n; ++i) {
        let x = strs[i].length;
        for (let j = 0; j < n; ++j) {
            if (i !== j && check(strs[i], strs[j])) {
                x = -1;
                break;
            }
        }
        ans = Math.max(ans, x);
    }
    return ans;
}

522. Longest Uncommon Subsequence II

Description

Solutions

Solution 1: Subsequence Judgment

Comments