522. Longest Uncommon Subsequence II LeetCode Solution
In this guide, you will get 522. Longest Uncommon Subsequence II LeetCode Solution with the best time and space complexity. The solution to Longest Uncommon Subsequence II problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Problem Statement of Longest Uncommon Subsequence II
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.
Complexity Analysis
Time Complexity: O(n^2\ell), where n = |\texttt{strs}| and \ell = \max(|\texttt{strs[i]}|)
Space Complexity: O(\Sigma |\texttt{strs[i]}|)
522. Longest Uncommon Subsequence II LeetCode Solution in C++
class Solution {
public:
int findLUSlength(vector<string>& strs) {
unordered_set<string> seen;
unordered_set<string> duplicates;
for (const string& str : strs)
if (seen.contains(str))
duplicates.insert(str);
else
seen.insert(str);
ranges::sort(strs, ranges::greater{},
[](const string& s) { return s.length(); });
for (int i = 0; i < strs.size(); ++i) {
if (duplicates.contains(strs[i]))
continue;
bool isASubsequence = false;
for (int j = 0; j < i; ++j)
isASubsequence |= isSubsequence(strs[i], strs[j]);
if (!isASubsequence)
return strs[i].length();
}
return -1;
}
private:
// Returns true if a is a subsequence of b.
bool isSubsequence(const string& a, const string& b) {
int i = 0;
for (const char c : b)
if (i < a.length() && c == a[i])
++i;
return i == a.length();
};
}; /* code provided by PROGIEZ */
522. Longest Uncommon Subsequence II LeetCode Solution in Java
class Solution {
public int findLUSlength(String[] strs) {
Set<String> seen = new HashSet<>();
Set<String> duplicates = new HashSet<>();
for (final String str : strs)
if (seen.contains(str))
duplicates.add(str);
else
seen.add(str);
Arrays.sort(strs, (a, b) -> b.length() - a.length());
for (int i = 0; i < strs.length; ++i) {
if (duplicates.contains(strs[i]))
continue;
boolean isASubsequence = false;
for (int j = 0; j < i; ++j)
isASubsequence |= isSubsequence(strs[i], strs[j]);
if (!isASubsequence)
return strs[i].length();
}
return -1;
}
// Returns true if a is a subsequence of b.
private boolean isSubsequence(final String a, final String b) {
int i = 0;
for (final char c : b.toCharArray())
if (i < a.length() && c == a.charAt(i))
++i;
return i == a.length();
}
} // code provided by PROGIEZ
522. Longest Uncommon Subsequence II LeetCode Solution in Python
class Solution:
def findLUSlength(self, strs: list[str]) -> int:
def isSubsequence(a: str, b: str) -> bool:
i = 0
j = 0
while i < len(a) and j < len(b):
if a[i] == b[j]:
i += 1
j += 1
return i == len(a)
seen = set()
duplicates = set()
for s in strs:
if s in seen:
duplicates.add(s)
seen.add(s)
strs.sort(key=lambda x: -len(x))
for i in range(len(strs)):
if strs[i] in duplicates:
continue
isASubsequence = False
for j in range(i):
isASubsequence |= isSubsequence(strs[i], strs[j])
if not isASubsequence:
return len(strs[i])
return -1 # code by PROGIEZ
