Description
Given a tree where each node has a character label, find the longest path where all adjacent nodes have different characters.
Examples
Input:
parent = [-1,0,0,1,1,2], s = "abacbe"Output:
3Explanation:
Longest path with different chars.
Input:
parent = [-1,0,0,0], s = "aabc"Output:
3Explanation:
Root 0 ('a') has children 1 ('a'), 2 ('b'), 3 ('c'). The longest valid path is 2-0-3 with chars 'b'-'a'-'c', all different, giving length 3.
Input:
parent = [-1,0,1,2,3,4], s = "abcdef"Output:
6Explanation:
All characters are different in this linear tree, so the longest path spans all 6 nodes.
Constraints
- •
1 ≤ n ≤ 10⁵