Learn
Practice
Interview
Resources
Newsletter
F
Toggle theme
0
F
0
Toggle menu
Animations
← Back to All Animations
Shortest Common Supersequence
Bookmark
Brute Force
LCS + Traceback
LCS + Merge
Input
Standard
No overlap
Identical
Longer
Custom
str1
=
abac
,
str2
=
cab
str1 =
"abac"
str2 =
"cab"
str2 (j)
str1 (i)
0
1
2
3
∅
c
a
b
0
1
2
3
4
∅
a
b
a
c
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
shortest string containing both "abac" and "cab" as subsequences?
str1 =
"abac"
str2 =
"cab"
str2 (j)
str1 (i)
0
1
2
3
∅
c
a
b
0
1
2
3
4
∅
a
b
a
c
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
shortest string containing both "abac" and "cab" as subsequences?
str1 =
"abac"
str2 =
"cab"
str2 (j)
str1 (i)
0
1
2
3
∅
c
a
b
0
1
2
3
4
∅
a
b
a
c
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
str1[
0
] =
'a'
vs str2[
1
] =
'a'
str1 =
"abac"
str2 =
"cab"
str2 (j)
str1 (i)
0
1
2
3
∅
c
a
b
0
1
2
3
4
∅
a
b
a
c
0
0
0
0
0
0
1
1
0
0
0
0
0
0
0
0
0
0
0
0
'a' != 'b'
dp[1][3] = max(
0
,
1
) =
1
str1 =
"abac"
str2 =
"cab"
str2 (j)
str1 (i)
0
1
2
3
∅
c
a
b
0
1
2
3
4
∅
a
b
a
c
0
0
0
0
0
0
1
1
0
0
1
0
0
0
0
0
0
0
0
0
'b' != 'a'
dp[2][2] = max(
1
,
0
) =
1
str1 =
"abac"
str2 =
"cab"
str2 (j)
str1 (i)
0
1
2
3
∅
c
a
b
0
1
2
3
4
∅
a
b
a
c
0
0
0
0
0
0
1
1
0
0
1
2
0
0
0
0
0
0
0
0
'a' != 'c'
dp[3][1] = max(
0
,
0
) =
0
str1 =
"abac"
str2 =
"cab"
str2 (j)
str1 (i)
0
1
2
3
∅
c
a
b
0
1
2
3
4
∅
a
b
a
c
0
0
0
0
0
0
1
1
0
0
1
2
0
0
1
0
0
0
0
0
str1[
2
] =
'a'
vs str2[
2
] =
'b'
str1 =
"abac"
str2 =
"cab"
str2 (j)
str1 (i)
0
1
2
3
∅
c
a
b
0
1
2
3
4
∅
a
b
a
c
0
0
0
0
0
0
1
1
0
0
1
2
0
0
1
2
0
1
0
0
str1[
3
] =
'c'
vs str2[
1
] =
'a'
str1 =
"abac"
str2 =
"cab"
str2 (j)
str1 (i)
0
1
2
3
∅
c
a
b
0
1
2
3
4
∅
a
b
a
c
0
0
0
0
0
0
1
1
0
0
1
2
0
0
1
2
0
1
1
2
scs
phase 2: answer length = 4 + 3 - lcs =
5
walk back from dp[4][3]
str1 =
"abac"
str2 =
"cab"
str2 (j)
str1 (i)
0
1
2
3
∅
c
a
b
0
1
2
3
4
∅
a
b
a
c
0
0
0
0
0
0
1
1
0
0
1
2
0
0
1
2
0
1
1
2
scs
b
a
c
'b' is shared
: write it once, move diagonally
str1 =
"abac"
str2 =
"cab"
str2 (j)
str1 (i)
0
1
2
3
∅
c
a
b
0
1
2
3
4
∅
a
b
a
c
0
0
0
0
0
0
1
1
0
0
1
2
0
0
1
2
0
1
1
2
scs
c
a
b
a
c
"cabac"
(length 5) contains both
algo
master
.
io
Step:
Shortest string that contains both "abac" and "cab" as subsequences?
0 / 33
Input
Standard
No overlap
Identical
Longer
Custom
str1
=
abac
,
str2
=
cab
0 / 33
algo
master
.
io
Step:
Shortest string that contains both "abac" and "cab" as subsequences?
