Learn
Practice
Newsletter
Resources
Mobile
New
F
Toggle theme
0
F
0
Toggle menu
Animations
← Back to All Animations
Longest Palindromic Subsequence
Bookmark
Input
Example 1
Example 2
Example 3
Custom
s
=
bbbab
s =
"bbbab"
end j
start i
0
1
2
3
4
b
b
b
a
b
0
1
2
3
4
b
b
b
a
b
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
longest palindromic subsequence inside "bbbab"? order kept, gaps allowed
s =
"bbbab"
end j
start i
0
1
2
3
4
b
b
b
a
b
0
1
2
3
4
b
b
b
a
b
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
longest palindromic subsequence inside "bbbab"? order kept, gaps allowed
s =
"bbbab"
len =
2
end j
start i
0
1
2
3
4
b
b
b
a
b
0
1
2
3
4
b
b
b
a
b
1
0
0
0
0
1
0
0
0
1
0
0
1
0
1
s[
0
..
1
] = "bb" ends
'b'
vs
'b'
s =
"bbbab"
len =
2
end j
start i
0
1
2
3
4
b
b
b
a
b
0
1
2
3
4
b
b
b
a
b
1
2
0
0
0
1
2
0
0
1
0
0
1
0
1
'b' == 'b'
dp[1][2] = 2 +
0 (nothing inside)
=
2
s =
"bbbab"
len =
2
end j
start i
0
1
2
3
4
b
b
b
a
b
0
1
2
3
4
b
b
b
a
b
1
2
0
0
0
1
2
0
0
1
1
0
1
0
1
s[
3
..
4
] = "ab" ends
'a'
vs
'b'
s =
"bbbab"
len =
3
end j
start i
0
1
2
3
4
b
b
b
a
b
0
1
2
3
4
b
b
b
a
b
1
2
0
0
0
1
2
0
0
1
1
0
1
1
1
s[
0
..
2
] = "bbb" ends
'b'
vs
'b'
s =
"bbbab"
len =
3
end j
start i
0
1
2
3
4
b
b
b
a
b
0
1
2
3
4
b
b
b
a
b
1
2
3
0
0
1
2
0
0
1
1
0
1
1
1
s[
1
..
3
] = "bba" ends
'b'
vs
'a'
s =
"bbbab"
len =
3
end j
start i
0
1
2
3
4
b
b
b
a
b
0
1
2
3
4
b
b
b
a
b
1
2
3
0
0
1
2
2
0
1
1
3
1
1
1
+2
'b' == 'b'
dp[2][4] = 2 +
dp[
3
][
3
] = 2 +
1
=
3
s =
"bbbab"
len =
4
end j
start i
0
1
2
3
4
b
b
b
a
b
0
1
2
3
4
b
b
b
a
b
1
2
3
3
0
1
2
2
0
1
1
3
1
1
1
'b' != 'a'
dp[0][3] = max(below
2
, left
3
) =
3
s =
"bbbab"
len =
5
end j
start i
0
1
2
3
4
b
b
b
a
b
0
1
2
3
4
b
b
b
a
b
1
2
3
3
0
1
2
2
3
1
1
3
1
1
1
len = 5
solve every substring of length 5
s =
"bbbab"
end j
start i
0
1
2
3
4
b
b
b
a
b
0
1
2
3
4
b
b
b
a
b
1
2
3
3
4
1
2
2
3
1
1
3
1
1
1
LPS =
"bbbb"
, length
4
algo
master
.
io
Step:
Longest palindromic subsequence inside "bbbab"?
0 / 26
Input
Example 1
Example 2
Example 3
Custom
s
=
bbbab
0 / 26
algo
master
.
io
Step:
Longest palindromic subsequence inside "bbbab"?
