Tree Path Without Twin Neighbours

Hard

You are given a tree of n nodes numbered 0 to n − 1 and rooted at node 0. It is described by the array parent: parent[i] is the parent of node i, and for the root parent[0] = -1. Each node carries a letter: node i is labelled labels[i]. A path is a sequence of distinct nodes where every two consecutive ones are joined by an edge; it may go both up and down. Find a path in which no two consecutive nodes carry the same letter, and return the largest possible number of nodes on it.

Example 1

parent=[-1, 0, 0, 1, 2, 2], labels='abbcac' → 5

The path 3 → 1 → 0 → 2 → 4 reads c, b, a, b, a: neighbours always differ, and it has 5 nodes.

Example 2

parent=[-1, 0, 1], labels='zzz' → 1

Every node has the same letter, so a path can only be a single node.

Example 3

parent=[-1, 0, 0, 0], labels='abac' → 3

Constraints

1 ≤ n ≤ 10⁵
len(parent) = len(labels) = n
parent[0] = -1, and 0 ≤ parent[i] < n otherwise
parent describes a valid tree
labels consists of lowercase English letters

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Tree Depth-First Search Graph Topological Sort Array String

Similar problems

Letter Order From a Dictionary Hard Expand a Template With Variables Medium Longest Uphill Walk Hard Ball Into the Hole Hard Uphill-Only Walks Hard

Input

parent=[-1, 0, 0, 1, 2, 2], labels='abbcac'

Expected

Run checks the first 3 tests in your browser. Submit checks all 15 tests on the server, hidden ones included.