Problem: 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 two strings is a string that is a subsequence of one but not the other.
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:
Input: strs = ["aba","cdc","eae"] Output: 3
Input: strs = ["aaa","aaa","aa"] Output: -1
Approach: This problem is an extension of the previous problem Longest Uncommon Subsequence I where we need to find the longest uncommon subsequence between two strings. Here instead of two strings we are given the array of strings.
Our approach remains same, we just need to find the longest substring which is not a subsequence of all the other substrings and its length will be our answer. We can sort strs using their length in descending order to make it little bit efficient. That's all!
Implementation in C#:
public int FindLUSlength(string[] strs)
{
Array.Sort(strs, (s1, s2) => {
return s2.Length.CompareTo(s1.Length);
});
for (int i = 0; i < strs.Length; ++i)
{
int j = 0;
for (; j < strs.Length; ++j)
{
if (i == j)
{
continue;
}
if (this.IsSubSequence(strs[i], strs[j]))
{
break;
}
}
if (j == strs.Length)
{
return strs[i].Length;
}
}
return -1;
}
private bool IsSubSequence(string s1, string s2)
{
int s1Itr = 0;
for (int s2Itr = 0; s1Itr < s1.Length && s2Itr < s2.Length; ++s2Itr)
{
if (s1[s1Itr] == s2[s2Itr])
{
++s1Itr;
}
}
return s1Itr == s1.Length;
}
Complexity: O(n^2 * len) where len is the length of longest string in strs.
No comments:
Post a Comment