Learn
Practice
Interview
Resources
Newsletter
F
Toggle theme
0
F
0
Toggle menu
Animations
← Back to All Animations
Longest Path With Different Adjacent Characters
Bookmark
Brute Force
Post-Order DFS
Topological Sort
Input
Example 1 (6 nodes)
Same char edge (4 nodes)
Linear chain (5 nodes)
Full binary tree (7 nodes)
Deep tree (9 nodes)
Custom
parent
=
[-1,0,0,1,1,2]
,
s
=
abacbe
maxLen =
1
a
b
a
c
b
e
try a walk from every node
maxLen =
1
a
b
a
c
b
e
try a walk from every node
maxLen =
1
a
len=
1
b
a
c
b
e
'b' ≠ 'a'
→ pathLen = 2
maxLen =
3
a
len=
1
b
a
c
b
e
'a' == 'a'
→ edge blocked
maxLen =
3
a
len=
2
b
start
a
c
b
e
dfs(0)
pathLen = 2
maxLen =
3
maxLen =
3
a
b
len=
1
a
c
b
e
'b' == 'b'
→ edge blocked
maxLen =
3
a
b
a
start
c
b
e
len=
2
dfs(5)
pathLen = 2
maxLen =
3
maxLen =
3
a
b
len=
2
a
c
start
b
e
dfs(1)
pathLen = 2
maxLen =
3
maxLen =
3
a
b
len=
2
a
c
start
b
e
'b' == 'b'
→ edge blocked
maxLen =
3
a
b
a
c
b
e
len=
1
dfs(5)
pathLen = 1
maxLen =
3
maxLen =
3
a
b
a
c
b
e
longest path = 3
a → b → c
algo
master
.
io
Step:
Find the longest path in this tree where no two adjacent nodes share a character
0 / 39
Input
Example 1 (6 nodes)
Same char edge (4 nodes)
Linear chain (5 nodes)
Full binary tree (7 nodes)
Deep tree (9 nodes)
Custom
parent
=
[-1,0,0,1,1,2]
,
s
=
abacbe
0 / 39
algo
master
.
io
Step:
Find the longest path in this tree where no two adjacent nodes share a character
