Longest Path with Distinct Adjacent Labels
Nodes in a tree carry category labels. A clean handoff chain is a path where no two directly connected nodes share a label. Find the length (in nodes) of the longest such chain.
Problem
Given a tree rooted at node 0 with n nodes described by a parent array (parent[0] = -1) and a string s where s[i] is the character label of node i, return the number of nodes on the longest path such that no two adjacent nodes on the path have the same label.
Input
An array parent of length n (parent[0] = -1) and a string s of length n.
Output
An integer: the node count of the longest valid path.
Constraints
- 1 <= n <= 100000
- parent describes a valid rooted tree; s consists of lowercase letters.
Examples
Example 1
Input
parent = [-1,0,0,1,1,2], s = "abacbe"
Output
3
Path 3 -> 1 -> 0 has labels c,b,a — all adjacent labels differ; length 3.
Example 2
Input
parent = [-1,0,0,0], s = "aabc"
Output
3
Through the root, two differing-label children give a length-3 path.