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:
In the brute force approach we will generate all the possible subsequences of all the strings and store their number of occurences in a hashmap. Longest subsequence whose frequency is equal to will be the required subsequence. And, if it is not found we will return .
\n\nComplexity Analysis
\nAlgorithm
\nBy 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.\nUsing 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 .
\nTo understand the method, look at the example given below:
\n\n!?!../Documents/595_Longest_Uncommon.json:1000,563!?!
\n\nComplexity Analysis
\nTime complexity : . where is the number of strings and is the average length of the strings.
\nSpace complexity : . Constant space required.
\nAlgorithm
\nIn 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.
\nIn 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.
\n\nComplexity Analysis
\nTime complexity : . where is the number of strings and is the average length of the strings.
\nSpace complexity : . Constant space required.
\nAnalysis written by: @vinod23
\n