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:
Works with negative numbers.
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⁵