Longest Uncommon Subsequence II LeetCode Solution

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

Longest Uncommon Subsequence II LeetCode Solution

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.

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

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;
    }
};Code language: PHP (php)

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();
    }
}Code language: JavaScript (javascript)

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
}Code language: JavaScript (javascript)

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 -1Code language: HTML, XML (xml)
Scroll to Top