2246. Longest Path With Different Adjacent Characters
Description
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: 3 Explanation: 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: 3 Explanation: 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 <= 105
0 <= parent[i] <= n - 1
for alli >= 1
parent[0] == -1
parent
represents a valid tree.s
consists of only lowercase English letters.
Solutions
Solution 1: Tree-shaped DP
First, we construct an adjacency list $g$ based on the array $parent$, where $g[i]$ represents all child nodes of node $i$.
Then we start DFS from the root node. For each node $i$, we traverse each child node $j$ in $g[i]$. If $s[i] \neq s[j]$, then we can start from node $i$, pass through node $j$, and reach a leaf node. The length of this path is $x = 1 + \textit{dfs}(j)$. We use $mx$ to record the longest path length starting from node $i$. At the same time, we update the answer $ans = \max(ans, mx + x)$ during the traversal process.
Finally, we return $ans + 1$.
The time complexity is $O(n)$, and the space complexity is $O(n)$, where $n$ is the number of nodes.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
|