Last updated on January 5th, 2025 at 12:57 am
Here, we see the longest uncommon subsequence II LeetCode Solution. This Leetcode problem is solved using different approaches in many programming languages, such as C++, Java, JavaScript, Python, etc.
List of all LeetCode Solution
Topics
String
Companies
Level of Question
Medium
Longest Uncommon Subsequence II LeetCode Solution
Table of Contents
1. 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
2. Coding Pattern Used in Solution
The coding pattern used in this code is Subsequence Checking. The key idea is to determine whether one string is a subsequence of another, which is done using a two-pointer technique.
3. Code Implementation in Different Languages
3.1 Longest Uncommon Subsequence II 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;
}
};
3.2 Longest Uncommon Subsequence II 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.3 Longest Uncommon Subsequence II 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
}
3.4 Longest Uncommon Subsequence II 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
4. Time and Space Complexity
| Time Complexity | Space Complexity | |
| C++ | O(n² * m) | O(n) |
| Java | O(n² * m) | O(1) |
| JavaScript | O(n² * m) | O(n) |
| Python | O(n² * m) | O(1) |
where, n is the number of strings and m is the average string length.
- Subsequence Checking: The core operation in all implementations is checking whether one string is a subsequence of another. This is done using a two-pointer approach.
- Sorting: Sorting the strings by length (in C++ and Python) helps optimize the search for the longest unique subsequence.
- Space Efficiency: The implementations are generally space-efficient, with minimal use of additional data structures.
- Performance Bottleneck: The nested loop for subsequence checking makes the time complexity quadratic in terms of the number of strings, with an additional factor of the average string length.