Learn
Practice
Interview
Resources
Newsletter
F
Toggle theme
0
F
0
Toggle menu
Animations
← Back to All Animations
Distinct Subsequences
Bookmark
Memoization
Bottom-Up DP
Space-Optimized
Input
Example 1
Example 2
Example 3
Custom
s
=
abc
,
t
=
ab
s
t
a
0
b
1
c
2
a
0
b
1
s
t
a
0
b
1
c
2
a
0
b
1
s
t
a
0
b
1
c
2
a
0
b
1
3,2
2,2
1,1
0,0
0,1
1,2
0,2
solve(3, 2)
s
t
a
0
b
1
c
2
a
0
b
1
3,2
2,2
1,1
0,0
0,1
1,2
0,2
solve(2, 2)
s
t
a
0
b
1
c
2
a
0
b
1
3,2
2,2
1,1
0,0
0,1
1,2
0,2
s[0] = t[0] = 'a'
s
t
a
0
b
1
c
2
a
0
b
1
3,2
2,2
1,1
0,0
1
0,1
1,2
0,2
the target is empty
s
t
a
0
b
1
c
2
a
0
b
1
3,2
2,2
1,1
0,0
1
0,1
0
1,2
0,2
s is exhausted, "a" is left
s
t
a
0
b
1
c
2
a
0
b
1
3,2
2,2
1,1
1
0,0
1
0,1
0
1,2
0,2
solve(1, 2)
memo
(1,1) = 1
s
t
a
0
b
1
c
2
a
0
b
1
3,2
2,2
1,1
1
0,0
1
0,1
0
1,2
0,2
0
s is exhausted, "ab" is left
memo
(1,1) = 1
s
t
a
0
b
1
c
2
a
0
b
1
3,2
2,2
1
1,1
1
0,0
1
0,1
0
1,2
0
0,2
0
memo[(2,2)] = 1
memo
(1,1) = 1
(1,2) = 0
(2,2) = 1
s
t
a
0
b
1
c
2
a
0
b
1
3,2
1
2,2
1
1,1
1
0,0
1
0,1
0
1,2
0
0,2
0
1 distinct way(s)
memo
(1,1) = 1
(1,2) = 0
(2,2) = 1
(3,2) = 1
algo
master
.
io
Step:
How many ways can "ab" be spelled by picking chars of "abc" in order?
0 / 20
Input
Example 1
Example 2
Example 3
Custom
s
=
abc
,
t
=
ab
0 / 20
algo
master
.
io
Step:
How many ways can "ab" be spelled by picking chars of "abc" in order?
