#2246
Longest Path With Different Adjacent Characters
candidate master · 1315 · lc hard +32 · verified · 54% accepted · 2,535 likes · top 46%
Description
You are given a rooted tree with n nodes labeled 0 to n - 1, rooted at node 0. It is described by a 0-indexed array parent of size n where parent[i] is the parent of node i, and parent[0] == -1.
You also have a string s of length n where s[i] is the character at node i.
Return the length of the longest path in the tree where every pair of adjacent nodes has different characters.
Example 1:
Input: parent = [-1,0,0,1,1,2], s = "abacbe"
Output: 3
Explanation: The longest path where each two adjacent nodes have different characters in the tree is the path: 0 -> 1 -> 3. The length of this path is 3, so 3 is returned.
It can be proven that there is no longer path that satisfies the conditions.
Example 2:
Input: parent = [-1,0,0,0], s = "aabc"
Output: 3
Explanation: The longest path where each two adjacent nodes have different characters is the path: 2 -> 0 -> 3. The length of this path is 3, so 3 is returned.
Code
1
2
3