522. Longest Uncommon Subsequence II (Medium)
Given a list of strings, you need to find the longest uncommon subsequence among them. The longest uncommon subsequence is defined as the longest subsequence of one of these strings and this subsequence should not be any subsequence of the other strings.
A subsequence is a sequence that can be derived from one sequence by deleting some characters without changing the order of the remaining elements. Trivially, any string is a subsequence of itself and an empty string is a subsequence of any string.
The input will be a list of strings, and the output needs to be the length of the longest uncommon subsequence. If the longest uncommon subsequence doesn't exist, return -1.
Example 1:
Input: "aba", "cdc", "eae"
Output: 3
Note:
- All the given strings' lengths will not exceed 10.
- The length of the given list will be in the range of [2, 50].
Solution
Approach #1 Brute Force[Accepted]
In the brute force approach we will generate all the possible $$2^n$$ subsequences of all the strings and store their number of occurences in a hashmap. Longest subsequence whose frequency is equal to 1 will be the required subsequence. And, if it is not found we will return -1.
c++ 119ms
class Solution {
public:
int findLUSlength(vector<string>& strs) {
unordered_map<string,int> m;
for (auto& s: strs) {
for (int i = 0; i < (1 << s.size()); ++i) {
string t;
for (int j = 0; j < s.size(); ++j) {
if ((i >> j) & 1) t += s[j];
}
++m[t];
}
}
int res = -1;
for (auto& a: m) {
if (a.second == 1) res = max(res,(int)a.first.size());
}
return res;
}
};
Complexity Analysis
- Time complexity: $$O(n*2^x)$$. where $$x$$ is the average length of the strings and $$n$$ is the total number of given strings.
- Space complexity: $$O(n2^x)$$. Hashmap of size $$n2^x$$ is used.
Approach #2 Checking Subsequence [Accepted]
Algorithm
By some analysis, we can note that if longest uncommon subsequence is there, then it will always be one of the string from the given list of strings. Using this idea, we can check each string that whether it is a subsequence of any other string. If a string is not a subsequence of any other string i.e. it is uncommon , we will return maximum length string out of them. If no string found, we will return -1−1.
To understand the method, look at the example given below:
c++ 3ms
class Solution {
bool isSubsequence(string& x, string& y) {
int i = 0;
for (int j = 0; j < y.size() && i < x.size(); ++j) {
if (x[i] == y[j]) ++i;
}
return i == x.size();
}
public:
int findLUSlength(vector<string>& strs) {
int res = -1;
for (int i = 0, j; i < strs.size(); ++i) {
for (j = 0; j < strs.size(); ++j) {
if (i == j) continue;
if (isSubsequence(strs[i], strs[j])) break;
}
if (j == strs.size()) res = max(res, (int)strs[i].size());
}
return res;
}
};
Complexity Analysis
- Time complexity: $$O(x*n^2)$$. where $$n$$ is the number of strings and $$x$$ is the average length of the strings.
- Space complexity: $$O(1)$$. Constant space required.
Approach #3 Sorting and Checking Subsequence [Accepted]
Algorithm
In the last approach, we needed to compare all the given strings and compare them for the subsequence criteria. We can save some computations if we sort the given set of strings based on their lengths initially.
In this approach, firstly we sort the given strings in decreasing order of their lengths. Then, we start off by comparing the longest string with all the other strings. If none of the other strings happens to be the subsequence of the longest string, we return the length of the longest string as the result without any need of further comparisons. If some string happens to be a subsequence of the longest string, we continue the same process by choosing the second largest string as the first string and repeat the process, and so on.
c++
class Solution {
bool isSubsequence(string& x, string& y) {
int i = 0;
for (int j = 0; j < y.size() && i < x.size(); ++j) {
if (x[i] == y[j]) ++i;
}
return i == x.size();
}
public:
int findLUSlength(vector<string>& strs) {
sort(strs.begin(), strs.end(), [](string& a, string& b) { return a.size() > b.size(); });
for (int i = 0, j; i < strs.size(); ++i) {
for (j = 0; j < strs.size(); ++j) {
if (i == j) continue;
if (isSubsequence(strs[i], strs[j])) break;
}
if (j == strs.size()) return strs[i].size();
}
return -1;
}
};
Complexity Analysis
- Time complexity: $$O(x*n^2)$$. where $$n$$ is the number of strings and $$x$$ is the average length of the strings.
- Space complexity: $$O(1)$$. Constant space required.