Solution


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 .

Complexity Analysis

  • 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]

Algorithm

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 .

Complexity Analysis

  • 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