Hard · Trees

Longest Path With Different Adjacent Characters

Given a tree of n nodes rooted at node 0 (parent[i] is the parent of node i, and parent[0] = −1) and a string s where s[i] is the letter of node i, return the number of nodes on the longest path in which no two adjacent nodes have the same letter.

Examples

Example 1

parent=[-1,0,0,1,1,2], s="abacbe" → 3

Output: 3 nodes

Example 2

parent=[-1,0,1,0,3], s="abcbd" → 5

Output: 5 nodes

Rebuild it in the studio

Read every interview problem free. Ten rooms need no account. A token opens a problem in full — Pro never counts.