# PROBLEM LINK:

Practice

Contest

**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.

# SOLUTIONS:

Editorialist's solution

asked
**25 Dec '14, 00:05**

5★darkshadows ♦

3.0k●93●164●187

accept rate:
12%

https://uva.onlinejudge.org/index.php?option=onlinejudge&page=show_problem&problem=1346