Learn
Practice
Interview
Resources
Newsletter
F
Toggle theme
0
F
0
Toggle menu
Animations
← Back to All Animations
Longest Common Subsequence
Bookmark
Input
Example 1
Example 2 (identical)
Example 3 (no match)
Example 4
Custom
text1
=
abcde
,
text2
=
ace
text1 =
"abcde"
text2 =
"ace"
text2 (j)
text1 (i)
0
1
2
3
∅
a
c
e
0
1
2
3
4
5
∅
a
b
c
d
e
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
longest subsequence common to "abcde" and "ace"? order kept, gaps allowed
text1 =
"abcde"
text2 =
"ace"
text2 (j)
text1 (i)
0
1
2
3
∅
a
c
e
0
1
2
3
4
5
∅
a
b
c
d
e
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
longest subsequence common to "abcde" and "ace"? order kept, gaps allowed
text1 =
"abcde"
text2 =
"ace"
text2 (j)
text1 (i)
0
1
2
3
∅
a
c
e
0
1
2
3
4
5
∅
a
b
c
d
e
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
text1[
0
] =
'a'
vs text2[
1
] =
'c'
text1 =
"abcde"
text2 =
"ace"
text2 (j)
text1 (i)
0
1
2
3
∅
a
c
e
0
1
2
3
4
5
∅
a
b
c
d
e
0
0
0
0
0
1
1
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
'a' != 'e'
dp[1][3] = max(top
0
, left
1
) =
1
text1 =
"abcde"
text2 =
"ace"
text2 (j)
text1 (i)
0
1
2
3
∅
a
c
e
0
1
2
3
4
5
∅
a
b
c
d
e
0
0
0
0
0
1
1
1
0
1
1
0
0
0
0
0
0
0
0
0
0
0
0
0
'b' != 'c'
dp[2][2] = max(top
1
, left
1
) =
1
text1 =
"abcde"
text2 =
"ace"
text2 (j)
text1 (i)
0
1
2
3
∅
a
c
e
0
1
2
3
4
5
∅
a
b
c
d
e
0
0
0
0
0
1
1
1
0
1
1
1
0
0
0
0
0
0
0
0
0
0
0
0
text1[
2
] =
'c'
vs text2[
0
] =
'a'
text1 =
"abcde"
text2 =
"ace"
text2 (j)
text1 (i)
0
1
2
3
∅
a
c
e
0
1
2
3
4
5
∅
a
b
c
d
e
0
0
0
0
0
1
1
1
0
1
1
1
0
1
2
0
0
0
0
0
0
0
0
0
text1[
2
] =
'c'
vs text2[
2
] =
'e'
text1 =
"abcde"
text2 =
"ace"
text2 (j)
text1 (i)
0
1
2
3
∅
a
c
e
0
1
2
3
4
5
∅
a
b
c
d
e
0
0
0
0
0
1
1
1
0
1
1
1
0
1
2
2
0
1
0
0
0
0
0
0
'd' != 'a'
dp[4][1] = max(top
1
, left
0
) =
1
text1 =
"abcde"
text2 =
"ace"
text2 (j)
text1 (i)
0
1
2
3
∅
a
c
e
0
1
2
3
4
5
∅
a
b
c
d
e
0
0
0
0
0
1
1
1
0
1
1
1
0
1
2
2
0
1
2
2
0
0
0
0
'd' != 'e'
dp[4][3] = max(top
2
, left
2
) =
2
text1 =
"abcde"
text2 =
"ace"
text2 (j)
text1 (i)
0
1
2
3
∅
a
c
e
0
1
2
3
4
5
∅
a
b
c
d
e
0
0
0
0
0
1
1
1
0
1
1
1
0
1
2
2
0
1
2
2
0
1
0
0
text1[
4
] =
'e'
vs text2[
1
] =
'c'
text1 =
"abcde"
text2 =
"ace"
text2 (j)
text1 (i)
0
1
2
3
∅
a
c
e
0
1
2
3
4
5
∅
a
b
c
d
e
0
0
0
0
0
1
1
1
0
1
1
1
0
1
2
2
0
1
2
2
0
1
2
3
LCS =
"ace"
, length
3
algo
master
.
io
Step:
Longest subsequence common to "abcde" and "ace"?
0 / 32
Input
Example 1
Example 2 (identical)
Example 3 (no match)
Example 4
Custom
text1
=
abcde
,
text2
=
ace
0 / 32
algo
master
.
io
Step:
Longest subsequence common to "abcde" and "ace"?
