2246. Longest Path With Different Adjacent Characters

Hard

2.2K

58

You are given a **tree** (i.e. a connected, undirected graph that has no cycles) **rooted** at node `0`

consisting of `n`

nodes numbered from `0`

to `n - 1`

. The tree is represented by a **0-indexed** array `parent`

of size `n`

, where `parent[i]`

is the parent of node `i`

. Since node `0`

is the root, `parent[0] == -1`

.

You are also given a string `s`

of length `n`

, where `s[i]`

is the character assigned to node `i`

.

Return *the length of the longest path in the tree such that no pair of adjacent nodes on the path have the same character assigned to them.*

**Example 1:**

Input:parent = [-1,0,0,1,1,2], s = "abacbe"Output:3Explanation:The longest path where each two adjacent nodes have different characters in the tree is the path: 0 -> 1 -> 3. The length of this path is 3, so 3 is returned. It can be proven that there is no longer path that satisfies the conditions.

**Example 2:**

Input:parent = [-1,0,0,0], s = "aabc"Output:3Explanation:The longest path where each two adjacent nodes have different characters is the path: 2 -> 0 -> 3. The length of this path is 3, so 3 is returned.

**Constraints:**

`n == parent.length == s.length`

`1 <= n <= 10`

^{5}`0 <= parent[i] <= n - 1`

for all`i >= 1`

`parent[0] == -1`

`parent`

represents a valid tree.`s`

consists of only lowercase English letters.

Accepted

65.4K

Submissions

117.1K

Acceptance Rate

55.8%

Seen this question in a real interview before?

1/4

Yes

No

Discussion (0)

Related Topics

Copyright ©️ 2023 LeetCode All rights reserved