Search⌘ K
AI Features
Home
Courses
Grokking the Coding Interview Patterns

Solution: Longest Path With Different Adjacent Characters

Understand how to apply topological sort to solve the problem of finding the longest path in a rooted tree where adjacent nodes must have different characters. Learn to calculate in-degrees, process nodes from leaves to root, track longest chains, and combine paths to determine the maximum valid path length efficiently.

We'll cover the following...

Statement

You are given a rooted tree with nn nodes, numbered from 00 to n−1n - 1, where the tree is connected, undirected, and has no cycles. The tree is represented by a 0-indexed array parent of size nn, where parent[i] is the parent of node ii. The root node is node 00, so parent[0] =−1= -1.

Additionally, you are provided a string s of length nn, where s[i] represents the character assigned to node ...