LeetCode 0522. Longest Uncommon Subsequence II Solution in Java, C++, Python & More | Explanation + Code

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

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 × 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).

PythonJavaC++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(code-box)

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; } }(code-box)

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; } };(code-box)

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 }(code-box)

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; }(code-box)