877. Changing Letters Path
A botanist records a tree of n lab specimens numbered 0 to n - 1, with specimen 0 as the root. parent[i] is the parent of specimen i, and parent[0] = -1. Every specimen i carries a one-letter label s[i].
A colour-shift path is a simple path in the tree (it may go up and down, and may be a single specimen) in which every two neighbouring specimens carry different letters. Return the largest number of specimens on any colour-shift path. A single specimen counts as a path of length 1, so the answer is always at least 1.
Example 1
- Input:
- parent = [-1,0,0,1,1,2,2], s = "abaabca"
- Output:
- 3
- Explanation:
The chain of nodes 3 - 1 - 0 carries letters a, b, a, so every neighbouring pair differs, giving 3 nodes; no 4-node path avoids an equal pair.
Example 2
- Input:
- parent = [-1,0,1,2], s = "zzzz"
- Output:
- 1
- Explanation:
Every edge joins two equal letters, so no edge may be used and the best path is a single node.
Constraints
- 1 ≤ n = parent.length = s.length ≤ 105
parent[0] = -1and0 ≤ parent[i] < ifor i ≥ 1sconsists of lowercase English letters
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 600 msC++ 150 msJava 300 msJavaScript 300 msTypeScript 300 ms
Expected complexity
- Time
- O(n)
- Space
- O(n)