Longest Uncommon Subsequence II – LeetCode Solution Java , Python 3, Python 2 , C , C++, Best and Optimal Solutions , All you need.
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
Constraints:
2 <= strs.length <= 50
1 <= strs[i].length <= 10
strs[i]
consists of lowercase English letters.
C++ Longest Uncommon Subsequence II LeetCode Solution
class Solution {
public:
int findLUSlength(vector<string>& strs) {
if (strs.empty()) return -1;
int rst = -1;
for(auto i = 0; i < strs.size(); ++i) {
int j = 0;
for(; j < strs.size(); ++j) {
if(i==j) continue;
if(LCS(strs[i], strs[j])) break; // strs[j] is a subsequence of strs[i]
}
// strs[i] is not any subsequence of the other strings.
if(j==strs.size()) rst = max(rst, static_cast<int>(strs[i].size()));
}
return rst;
}
// iff a is a subsequence of b
bool LCS(const string& a, const string& b) {
if (b.size() < a.size()) return false;
int i = 0;
for(auto ch: b) {
if(i < a.size() && a[i] == ch) i++;
}
return i == a.size();
}
};
Java Longest Uncommon Subsequence II LeetCode Solution
public int findLUSlength(String[] strs) {
Arrays.sort(strs, new Comparator<String>() {
public int compare(String o1, String o2) {
return o2.length() - o1.length();
}
});
Set<String> duplicates = getDuplicates(strs);
for(int i = 0; i < strs.length; i++) {
if(!duplicates.contains(strs[i])) {
if(i == 0) return strs[0].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 a, String b) {
int i = 0, j = 0;
while(i < a.length() && j < b.length()) {
if(a.charAt(i) == b.charAt(j)) j++;
i++;
}
return j == b.length();
}
private Set<String> getDuplicates(String[] strs) {
Set<String> set = new HashSet<String>();
Set<String> duplicates = new HashSet<String>();
for(String s : strs) {
if(set.contains(s)) duplicates.add(s);
set.add(s);
}
return duplicates;
}
Python 3 Longest Uncommon Subsequence II LeetCode Solution
class Solution:
def findLUSlength(self, words):
def isSubsequence(s, t):
t = iter(t)
return all(c in t for c in s)
words.sort(key = lambda x:-len(x))
for i, word in enumerate(words):
if all(not isSubsequence(word, words[j]) for j in range(len(words)) if j != i):
return len(word)
return -1
Array-1180
String-562
Hash Table-412
Dynamic Programming-390
Math-368
Sorting-264
Greedy-257
Depth-First Search-256
Database-215
Breadth-First Search-200
Tree-195
Binary Search-191
Matrix-176
Binary Tree-160
Two Pointers-151
Bit Manipulation-140
Stack-133
Heap (Priority Queue)-117
Design-116
Graph-108
Simulation-103
Prefix Sum-96
Backtracking-92
Counting-86
Sliding Window-73
Linked List-69
Union Find-66
Ordered Set-48
Monotonic Stack-47
Recursion-43
Trie-41
Binary Search Tree-40
Divide and Conquer-40
Enumeration-39
Bitmask-37
Queue-33
Memoization-32
Topological Sort-31
Geometry-30
Segment Tree-27
Game Theory-24
Hash Function-24
Binary Indexed Tree-21
Interactive-18
Data Stream-17
String Matching-17
Rolling Hash-17
Shortest Path-16
Number Theory-16
Combinatorics-15
Randomized-12
Monotonic Queue-9
Iterator-9
Merge Sort-9
Concurrency-9
Doubly-Linked List-8
Brainteaser-8
Probability and Statistics-7
Quickselect-7
Bucket Sort-6
Suffix Array-6
Minimum Spanning Tree-5
Counting Sort-5
Shell-4
Line Sweep-4
Reservoir Sampling-4
Eulerian Circuit-3
Radix Sort-3
Strongly Connected Componen-t2
Rejection Sampling-2
Biconnected Component-1