548. Same Label Below
A seed vault stores its drawers in a tree of n compartments numbered 0 to n - 1, with compartment 0 as the main entrance (the root). The array edges lists the two-way passages as pairs [u, v]. The string labels has length n, and labels[i] is the lowercase letter marking the seed type kept in compartment i.
The subtree of compartment i is compartment i together with every compartment reached by walking away from the entrance through it. Return an array answer of length n in which answer[i] is the number of compartments in the subtree of i (including i itself) whose label equals labels[i].
Example 1
- Input:
- n = 7edges = [[0,1],[0,2],[1,3],[1,4],[2,5],[2,6]]labels = "abbabba"
- Output:
- [3,2,2,1,1,1,1]
- Explanation:
Node 0 (label a) sees a at positions 0, 3 and 6; node 1 (label b) sees b at 1 and 4; node 2 sees b at 2 and 5; each leaf counts only itself.
Example 2
- Input:
- n = 5edges = [[0,1],[1,2],[2,3],[3,4]]labels = "aaaaa"
- Output:
- [5,4,3,2,1]
- Explanation:
Every node shares its label with everything below it, so each answer is the size of its subtree.
Constraints
1 ≤ n ≤ 105
edges.length == n - 1, 0 ≤ u, v < n; the edges form a tree and node 0 is the root
labels.length == n, and each character is a lowercase letter from 'a' to 'z'
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 1,600 msC++ 400 msJava 800 msJavaScript 800 msTypeScript 800 ms
Expected complexity
- Time
- O(26 * n)
- Space
- O(26 * n)