Approach #1 Brute Force [Time Limit Exceeded]
In the brute force approach we will generate all the possible subsequences of both 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 .
- Time complexity : . where and are the lengths of strings and respectively . Number of subsequences will be .
- Space complexity : . subsequences will be generated.
Approach #2 Simple Solution[Accepted]
Simple analysis of this problem can lead to an easy solution.
These three cases are possible with string and :-
. If both the strings are identical, it is obvious that no subsequence will be uncommon. Hence, return -1.
and . Example: and . In this case we can consider any string i.e. or as a required subsequence, as out of these two strings one string will never be a subsequence of other string. Hence, return or .
. Example and . In this case we can consider bigger string as a required subsequence because bigger string can't be a subsequence of smaller string. Hence, return .
Time complexity : . where and are the lengths of strings and respectively. Here equals method will take time .
Space complexity : . No extra space required.
Analysis written by: @vinod23