Regraft Under the Same Letter

Medium

You are given a tree of n nodes numbered 0 to n - 1, rooted at node 0. It is described by the array parent: parent[i] is the parent of node i, and parent[0] = -1. Each node also carries a letter, labels[i]. All non-root nodes are regrafted at the same time: node x looks among its ancestors in the original tree for the closest one with the same letter as its own. If there is one, x and its whole subtree are moved to become that ancestor's child; otherwise x stays where it is. Return an array whose i-th element is the number of nodes in the subtree of node i in the resulting tree, counting i itself.

Example 1

parent=[-1, 0, 1, 2], labels="abab" → [4, 2, 1, 1]

Node 2 (letter a) moves to its closest ancestor with the same letter, the root 0. Node 3 (letter b) moves to node 1. Now the root has children 1 and 2, and node 1 has child 3.

Example 2

parent=[-1, 0, 0], labels="xyz" → [3, 1, 1]

All letters differ, so nobody moves.

Constraints

1 ≤ n ≤ 2 · 10⁵
len(parent) = len(labels) = n
parent[0] = -1, and parent describes a valid tree rooted at 0
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 Array Hash Table String

Similar problems

Smallest Shared Territory Medium Palindromic Subtrees Hard Stop a Process Branch Medium Path Totals in a Coded Tree Medium Merge Contact Cards Medium

Input

parent=[-1, 0, 1, 2], labels="abab"

Expected

[4, 2, 1, 1]

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