## 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