Learn
Practice
Interview
Resources
Newsletter
F
Toggle theme
0
F
0
Toggle menu
Animations
← Back to All Animations
Longest String Chain
Bookmark
Brute Force
Sorting + DP
Hash Map DP
Input
Example 1
Example 2
Example 3 (no chain)
Custom
words
=
[a, b, ba, bca, bda, bdca]
maxLen =
1
words
a
b
ba
bca
bda
bdca
dp
?
?
?
?
?
?
0
1
2
3
4
5
longest chain where each word is the previous one plus a letter?
maxLen =
1
words
a
b
ba
bca
bda
bdca
dp
?
?
?
?
?
?
0
1
2
3
4
5
longest chain where each word is the previous one plus a letter?
maxLen =
1
words
a
b
ba
bca
bda
bdca
dp
1
?
?
?
?
?
0
1
2
3
4
5
word
dp["a"] =
1
longest chain so far:
1
maxLen =
1
words
a
b
ba
bca
bda
bdca
dp
1
1
?
?
?
?
0
1
2
3
4
5
word
dp["b"] =
1
longest chain so far:
1
maxLen =
1
+1
words
a
b
b
a
bca
bda
bdca
dp
1
1
2
?
?
?
0
1
2
3
4
5
word
drop
'a'
→
"b"
: a word with chain
1
, candidate
2
maxLen =
2
words
a
b
ba
b
c
a
bda
bdca
dp
1
1
2
?
?
?
0
1
2
3
4
5
word
drop
'b'
→
"ca"
is not one of our words
maxLen =
3
words
a
b
ba
bca
bda
bdca
dp
1
1
2
3
?
?
0
1
2
3
4
5
word
dp["bca"] =
3
longest chain so far:
3
maxLen =
3
+1
words
a
b
ba
bca
b
d
a
bdca
dp
1
1
2
3
?
?
0
1
2
3
4
5
word
drop
'd'
→
"ba"
: a word with chain
2
, candidate
3
maxLen =
3
words
a
b
ba
bca
bda
bdca
dp
1
1
2
3
3
?
0
1
2
3
4
5
word
"bdca"
delete each letter, does a shorter word appear?
maxLen =
3
+1
words
a
b
ba
bca
bda
b
d
c
a
dp
1
1
2
3
3
4
0
1
2
3
4
5
word
drop
'd'
→
"bca"
: best = dp["bca"] + 1 =
4
maxLen =
4
words
a
b
ba
bca
bda
bdca
dp
1
1
2
3
3
4
0
1
2
3
4
5
a → ba → bca → bdca
(length
4
)
algo
master
.
io
Step:
Longest chain of words where each one is the previous plus one letter?
0 / 32
Input
Example 1
Example 2
Example 3 (no chain)
Custom
words
=
[a, b, ba, bca, bda, bdca]
0 / 32
algo
master
.
io
Step:
Longest chain of words where each one is the previous plus one letter?
