Learn
Practice
Interview
Resources
Newsletter
F
Toggle theme
0
F
0
Toggle menu
Animations
← Back to All Animations
Longest Palindromic Subsequence
Bookmark
Memoization
Tabulation
Space-Optimized
LCS Reduction
Input
Example 1
Example 2
Example 3
Custom
s
=
bbbab
s
b
0
b
1
b
2
a
3
b
4
s
b
0
b
1
b
2
a
3
b
4
s
b
0
b
1
b
2
a
3
b
4
0,4
1,3
2,3
3,3
2,2
1,2
2,1
solve(0, 4)
s
b
0
b
1
b
2
a
3
b
4
0,4
1,3
2,3
3,3
2,2
1,2
2,1
solve(1, 3)
s
b
0
b
1
b
2
a
3
b
4
0,4
1,3
2,3
3,3
2,2
1,2
2,1
s[2] = 'b' vs s[3] = 'a'
s
b
0
b
1
b
2
a
3
b
4
0,4
1,3
2,3
3,3
1
2,2
1,2
2,1
'a' on its own
s
b
0
b
1
b
2
a
3
b
4
0,4
1,3
2,3
3,3
1
2,2
1
1,2
2,1
'b' on its own
s
b
0
b
1
b
2
a
3
b
4
0,4
1,3
2,3
1
3,3
1
2,2
1
1,2
2,1
solve(1, 2)
memo
(2,3) = 1
s
b
0
b
1
b
2
a
3
b
4
0,4
1,3
2,3
1
3,3
1
2,2
1
1,2
2,1
0
the window is empty
memo
(2,3) = 1
s
b
0
b
1
b
2
a
3
b
4
0,4
1,3
2
2,3
1
3,3
1
2,2
1
1,2
2
2,1
0
memo[(1,3)] = 2
memo
(2,3) = 1
(1,2) = 2
(1,3) = 2
s
b
0
b
1
b
2
a
3
b
4
0,4
4
1,3
2
2,3
1
3,3
1
2,2
1
1,2
2
2,1
0
longest palindromic subsequence = 4
memo
(2,3) = 1
(1,2) = 2
(1,3) = 2
(0,4) = 4
algo
master
.
io
Step:
Longest palindromic subsequence inside "bbbab"?
0 / 20
Input
Example 1
Example 2
Example 3
Custom
s
=
bbbab
0 / 20
algo
master
.
io
Step:
Longest palindromic subsequence inside "bbbab"?
