Longest Uncommon Subsequence II Problem
Description
LeetCode Problem 522.
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:
1
2
Input: strs = ["aba","cdc","eae"]
Output: 3
Example 2:
1
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.
Sample C++ Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
// Desending order of string size
bool cmp(pair<string,int> &a, pair<string,int> &b) {
return a.first.size() > b.first.size();
}
// Return true for s1 = abc, s2 = aebece
bool isSubStringOf(string &s1, string &s2){
int i = 0, j = 0;
while (i < s1.size()) {
while (j < s2.size() && s1[i] != s2[j])
j++;
if (j == s2.size())
return false;
i++;
j++;
}
return true;
}
class Solution {
public:
int findLUSlength(vector<string>& strs) {
// Define a string to int map to save the frequency of each string
unordered_map<string, int> mp;
for (const auto& str : strs)
mp[str]++;
// Define a vector of map element pair and sort it in descending order of string size
vector<pair<string, int>> vec;
for (const auto& m : mp)
vec.push_back(m);
sort(vec.begin(), vec.end(), cmp);
// For each string in the sorted vector, if all the other string coming before it is
// NOT super string of it then we use its size as LUS. If each pair of string have
// sub string relation then the longest uncommon subsequence doesn't exist
for (int i = 0; i < vec.size(); i++) {
if (1 == vec[i].second) {
int j = 0;
for (; j < i; j++)
if (isSubStringOf(vec[i].first, vec[j].first))
break;
if (j == i)
return vec[i].first.size();
}
}
return -1;
}
};