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


&nbsp;
Example 1:
Input: strs = ["aba","cdc","eae"]
Output: 3
Example 2:
Input: strs = ["aaa","aaa","aa"]
Output: -1

&nbsp;
Constraints:


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


class Solution:
    def findLUSlength(self, s: List[str]) -> int:
        def lcs(X, Y):
            m = len(X)
            n = len(Y)
            L = [[None]*(n + 1) for i in range(m + 1)]
            for i in range(m + 1):
                for j in range(n + 1):
                    if i == 0 or j == 0 :
                        L[i][j] = 0
                    elif X[i-1] == Y[j-1]:
                        L[i][j] = L[i-1][j-1]+1
                    else:
                        L[i][j] = max(L[i-1][j], L[i][j-1])
            return L[m][n]
            
        k = 0 
        mp = {}
        for i in s:
            if len(i) not in mp:
                mp[len(i)] = [i]
            else:
                mp[len(i)].append(i)
            k = max(k , len(i))
        
        t = k
        while(k):
            if k not in mp:
              k -= 1
            else:
                curr = mp[k]
                n = len(curr)
                for i in range(n):
                    f = 0
                    for j in range(n):
                        if(i != j and curr[i] == curr[j]):
                            f = 1
                            break
                    if(not(f)):
                        ff = 0 
                        for j in range(k+1 , t+1):
                            if(ff):break
                            if(j not in mp): continue
                            for jj in mp[j]:
                                if(lcs(curr[i] , jj) == len(curr[i])):
                                    ff = 1
                                    break
                        if(not(ff)):return len(curr[i])
                k-=1
                
        return -1

        

        
class Solution {
    public int findLUSlength(String[] strs) {
        Arrays.sort(strs,(a,b) -> b.length() - a.length()); // sort descending order by length
         // store the frequency of all strings in array
        Map<String,Integer> map = new HashMap<>();
        for(String s : strs) map.put(s,map.getOrDefault(s,0)+1);

        for(int i=0;i<strs.length;i++){
            if(map.get(strs[i]) != 1) continue; // string is not unique
            int j;
            for(j=0;j<i;j++){
                if(isSubsequence(strs[i],strs[j])) break;
            }
            // if it is not a subsequence of any other larger string
             if(j == i) return strs[i].length();
        }
        return -1; // no string satisfies the criterion
    }
    public boolean isSubsequence(String a, String b){
        int i=0,j=0;
        while(i<a.length() && j<b.length())
            if(a.charAt(i) == b.charAt(j++)) i++;
        return i == a.length();
    }
}
class Solution {
private:
    bool isCommon(string &s,string &t){
        int index=0;
        for(int i=0;i<s.size();i++){
            if(s[i]==t[index]){
                if(++index==t.size()){
                    return true;
                }
            }
        }
        return false;
    }
    bool isUncommon(vector<string>&strs,int index){
        for(int i=0;i<strs.size() and strs[index].size()<=strs[i].size();i++){
            if(index!=i and isCommon(strs[i],strs[index])){
                return false;
            }
        }
        return true;
    }
public:
    int findLUSlength(vector<string>& strs) {
        sort(strs.begin(),strs.end(),[](string &s,string &t){
            return s.size()>t.size();
        });
        int ans=-1;
        for(int i=0;i<strs.size();i++){
            if(isUncommon(strs,i)){
                ans=strs[i].size();
                break;
            } 
        }
        return ans;
    }
};
var findLUSlength = function(strs) {
	strs.sort((a, b) => b.length - a.length);
	const isSubsequence = (a, b) => {
		const A_LENGTH = a.length;
		const B_LENGTH = b.length;
		if (A_LENGTH > B_LENGTH) return false;
		if (a === b) return true;
		const matches = [...b].reduce((pos, str) => {
			return a[pos] === str ? pos + 1 : pos;
		}, 0);
		return matches === A_LENGTH;
	}

	for (let a = 0; a < strs.length; a++) {
		let isUncommon = true;

		for (let b = 0; b < strs.length; b++) {
			if (a === b) continue;
			if (isSubsequence(strs[a], strs[b])) {
				isUncommon = false;
				break;
			}
		}
		if (isUncommon) return strs[a].length;

	}
	return -1;
};
Longest Uncommon Subsequence II