2246. Longest Path With Different Adjacent Characters
# Problem
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 0indexed 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.
# Insight
After reading the problem, the first idea in my mind is DFS, since that’s the common way to solve Tree problems.
Given a node, we can determine the longest path that starts at from it by its children. There are some cases we might consider:
# Without any children
This is the simplest case, and the longest path is 1
# At least one child
If the current node label and its child are the same, so the longest path if we follow that path is
0
. But we still have to continue DFS for that child, since might be the case when the longest path is started by that child. For example:If there are more than two children, we have to find out the top 2 longest path, and the longest path is
sum of that two path + 1
. Look at the Example 2 above to find out why.
# Submission

