Last updated on July 18th, 2024 at 02:35 am

Here, We see Longest Uncommon Subsequence II LeetCode Solution. This Leetcode problem is done in many programming languages like C++, Java, JavaScript, Python, etc. with different approaches.

List of all LeetCode Solution

Topics

String

Companies

Google

Level of Question

Medium

Longest Uncommon Subsequence II LeetCode Solution

Problem Statement

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

1. Longest Uncommon Subsequence II LeetCode Solution C++

bool cmp(pair<string,int> &a, pair<string,int> &b)
{
    return a.first.size() > b.first.size();
}

bool isS1subsOfS2(string &s1, string &s2){
    int j = 0, i = 0;
    for(; i < s1.size(); ++i){
        while(j < s2.size() && s1[i] != s2[j]) ++j;
        if(j == s2.size())
           return false;
        ++j;
    }
    return true;
}
class Solution {
public:
    int findLUSlength(vector<string>& strs) {
        unordered_map<string,int> m;
        for(int i = 0; i < strs.size(); ++i)
          ++m[strs[i]];
        vector<pair<string,int>> v;
        for(auto it = m.begin(); it != m.end(); ++it)
           v.push_back(*it);
        sort(v.begin(),v.end(),cmp);
        for(int i = 0; i < v.size(); ++i)
        {
           if(v[i].second == 1){
               int j = 0;
               for(; j < i; ++j)
                 if(isS1subsOfS2(v[i].first,v[j].first))
                     break;
               if(j == i) return v[i].first.size();
           }
        }
        return -1;
    }
};

2. Longest Uncommon Subsequence II LeetCode Solution Java

class Solution {
    public int findLUSlength(String[] strs) {
        int max=-1;
        for(int i=0;i<strs.length;i++){
            boolean flag=false;
            int cur=strs[i].length();
            for(int j=0;j<strs.length;j++){
                if(i!=j && isSubsequence(strs[i], strs[j])){
                    flag=true;
                    break;
                }
            }
            if(!flag){
                max=Math.max(max,cur);
            }
        }
        return max;
    }
    private boolean isSubsequence(String a, String b){
        if(a.equals(b)) return true;
        int i=0;
        int j =0;
        while(i<a.length() && j<b.length()){
            if(a.charAt(i) == b.charAt(j++)){
                i++;
            }
        }
        return i==a.length();
    }
}

3. Longest Uncommon Subsequence II Solution JavaScript

var findLUSlength = function(strs) {
    const ignore = {} 
    for(let a of strs){
        ignore[a] = ignore[a] ? -1 : 50;
    } 
    for(let a of strs) {
        for(let b of strs){
            if(a===b) continue;
            const len = getSubSeq(a,b)
            if(len<0) ignore[a] = -1; else ignore[a] = Math.min(ignore[a], len);
        }
    }    
    return Math.max(...Object.values(ignore))
};

function getSubSeq(a, b){
    let j = 0
    let match = 0
    for(let ai of a)
        while(j<b.length){
            if(ai===b[j++]){
                match++
                break
            }
    }
    return match === a.length ? -1 : a.length
}

4. Longest Uncommon Subsequence II Solution Python

class Solution(object):
    def findLUSlength(self, strs):
        def isSubsequence(a, b):
            i = 0
            for char in b:
                if i < len(a) and a[i] == char:
                    i += 1
            return i == len(a)
        strs.sort(key=lambda s: -len(s))
        for i, s in enumerate(strs):
            if all(not isSubsequence(s, strs[j]) for j in range(len(strs)) if j != i):
                return len(s)
        return -1