PROBLEM LINK:
Editorialist: Lalit Kundu
DIFFICULTY:
EASY
PRE-REQUISITES:
Dynamic Programming
PROBLEM:
Given two sequences S1 and S2 of characters {A,T,C,G} find the length of the smallest sequence that contains both the given sequences as subsequence.
Length of both sequences less than 1000.
EXPLANATION:
Let’s say dp[i][j] denotes the answer for first i characters of S1 and first j characters of S2.
Now, recurrences will be as follows:
//note we are using 1 indexing.
//if both characters are matching
if S1[i-1]==S2[j-1]:
dp[i][j]= 1 + dp[i-1][j-1]
//characters don't match
//first try to place S1[i] at the end
//then try to place S2[j] at the end
//take minimum of both
else:
dp[i][j] = 1 + min(dp[i][j-1] , dp[i-1][j])
Note the base case:
If i<1, S1 doesn’t exist, so answer will be j.
If j<1, S2 doesn’t exist, so answer will be i.
Complexity: O(len(S1) * len(S2)).
Very basic DP similar to this is LCS.
Infact, another intuitive way to look at this problem is that we need to overlap as many characters of S1 and S2. So our answer would be len(S1)+len(S2)-len(LCS(S1,S2)), where LCS(X,Y) is longest common subsequence of strings X and Y.
IMPLEMENTATION:
Recursive DP with memoization is always easy to implement. See editorialist’s code for implemenation details.