Algorithm
Problem Name: 522. Longest Uncommon Subsequence II
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 <= 501 <= strs[i].length <= 10strs[i]consists of lowercase English letters.
Code Examples
#1 Code Example with Javascript Programming
Code -
Javascript Programming
const findLUSlength = function(strs) {
strs.sort((a, b) => b.length - a.length)
const dup = getDuplicates(strs)
for(let i = 0; i < strs.length; i++) {
if(!dup.has(strs[i])) {
if(i === 0) return strs[0].length
for(let j = 0; j < i; j++) {
if(isSubsequence(strs[j], strs[i])) break
if(j === i - 1) return strs[i].length
}
}
}
return -1
};
function isSubsequence(a, b) {
let i = 0, j = 0
while(i < a.length && j < b.length) {
if(a.charAt(i) === b.charAt(j)) j++
i++
}
return j === b.length
}
function getDuplicates(arr) {
const set = new Set()
const dup = new Set()
for(let el of arr) {
if(set.has(el)) dup.add(el)
else set.add(el>
}
return dup
}
Input
strs = ["aba","cdc","eae"]
Output
3
#2 Code Example with Python Programming
Code -
Python Programming
class Solution:
def findLUSlength(self, strs):
def find(s, t):
i = 0
for c in t:
if c == s[i]: i += 1
if i == len(s): return True
return False
for s in sorted(strs, key=len, reverse=True):
if sum(find(s, t) for t in strs) == 1: return len(s)
return -1
Input
strs = ["aba","cdc","eae"]
Output
3