## DEV Community Rohith V

Posted on • Updated on

# Leetcode 522 - Longest Uncommon Subsequence II

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

## Test Cases :

Example 1:

Input: strs = ["aba","cdc","eae"]
Output: 3

Example 2:

Input: strs = ["aaa","aaa","aa"]
Output: -1

## Constraints :

1 <= strs.length <= 50
1 <= strs[i].length <= 10
strs[i] consists of lowercase English letters.

## Approach :

1) We will be sorting the string array in the reverse order based on the each string length.

`Arrays.sort(strs, (s1, s2) -> Integer.compare(s2.length(), s1.length()));`

2) Then we will be finding the duplicates present inside the array. If there are no duplicate, then the answer will be the length of largest string.

``````public Set<String> findDuplicate(String [] strs) {
Set<String> store = new HashSet<>();
Set<String> duplicate = new HashSet<>();
for (String s : strs) {
if (store.contains(s)) {
}
else {
}
}
return duplicate;
}
``````

3) Now check the other string that are not duplicate and skip which are subsequence.

4) If a string is not duplicate and i == 0, then that strings length is the answer what we are looking for.

5) Else we check this string with other strings and check whether it is a subsequence. If a subsequence then we will be skipping, otherwise if j == i - 1, then that strings length will be our answer.

``````for (int i=0; i<strs.length; i++) {
if (!duplicates.contains(strs[i])) {
if (i == 0)
return strs[i].length();
for (int j=0; j<i; j++) {
if (isSubsequence(strs[j], strs[i]))
break;
if (j == i - 1)
return strs[i].length();
}
}
}
return -1;
}

public boolean isSubsequence(String s1, String s2) {
int i = 0;
int j = 0;
while (i < s1.length() && j < s2.length()) {
if (s1.charAt(i) == s2.charAt(j)) {
j++;
}
i++;
}
return j == s2.length();
}
``````

## Final Code :

``````class Solution {
public int findLUSlength(String[] strs) {
if (strs == null || strs.length == 0)
return -1;
// 1. sort in reversing order
Arrays.sort(strs, (s1, s2) -> Integer.compare(s2.length(), s1.length()));
// 2. Find the duplicates if any
// if no duplicates then the longest string is the answer
Set<String> duplicates = findDuplicate(strs);
if (duplicates.size() == 0) {
return strs.length();
}
// check for other strings that are not duplicate
// skip which are common
for (int i=0; i<strs.length; i++) {
if (!duplicates.contains(strs[i])) {
if (i == 0)
return strs[i].length();
for (int j=0; j<i; j++) {
if (isSubsequence(strs[j], strs[i]))
break;
if (j == i - 1)
return strs[i].length();
}
}
}
return -1;
}

public boolean isSubsequence(String s1, String s2) {
int i = 0;
int j = 0;
while (i < s1.length() && j < s2.length()) {
if (s1.charAt(i) == s2.charAt(j)) {
j++;
}
i++;
}
return j == s2.length();
}

public Set<String> findDuplicate(String [] strs) {
Set<String> store = new HashSet<>();
Set<String> duplicate = new HashSet<>();
for (String s : strs) {
if (store.contains(s)) {
}
else {
}
}
return duplicate;
}
}
``````

## Time and Space Complexity :

• Time - O(n ^ 2) where n is the length of array

• Space - O(n) where we are making use of extra set to note the duplicates

DEV Community

## The AI Brief

### AI generated git commit messages

Minimize the struggle of remembering what you just coded. AI-generated commits make it easier to manage projects and keep track of changes. The Nutlope/aicommits project demonstrates how AI can improve commit messages.

### I open sourced an AI that creates any UI in seconds

Make AI-generated user interfaces a breeze. This open-source project harnesses the power of generative AI technologies like chatGPT to create versatile, quick, and intuitive UI components.

### Use AI to commit like a PRO in 1 second

Upgrade your commit message game with AI. Boost your productivity by using ChatGPT to generate commit messages and avoid context switching. OpenCommit is an open-source library that helps you achieve this easily.

### Build your own ChatGPT starter kit

Train AI models on custom data for improved domain-specific knowledge. Combine the power of WebView technologies and this starter kit to train your ChatGPT model on specific websites, allowing for better-optimized outcomes.