Solution: Longest Path With Different Adjacent Characters

Statement

You are given a rooted tree with $n$ nodes, numbered from $0$ to $n - 1$, where the tree is connected, undirected, and has no cycles. The tree is represented by a 0-indexed array parent of size $n$, where parent[i] is the parent of node $i$. The root node is node $0$, so parent[0] $= -1$.

Additionally, you are provided a string s of length $n$, where s[i] represents the character assigned to node $i.$

Your task is to find the length of the longest path in the tree where no two consecutive nodes on the path share the same character. Return the length of this path.

Constraints:

• $n$ $=$ parent.length $=$ s.length

• $1 \leq n \leq 10^5$

• $0 \leq$ parent[i] $\leq n - 1$ for all $i \geq 1$

• parent[0] $= -1$

• parent represents a valid tree.

• s consists of only lowercase English letters.

Solution

We start by calculating the number of children (or in-degrees) for each node, based on the parent array. Nodes with no children (leaf nodes) are processed first, as they form the base of our calculations.

As we process the tree in reverse topological order (from leaves to root), we track the longest valid chain for each node. For each node in the queue, if the character at the parent node is different from the current node's character, we update the longest path at the parent node by adding the longest chain from the child node to the parent's existing longest chain. Specifically, for each child, if the characters are distinct, we calculate the child’s longest chain (i.e., the number of valid nodes in the longest path starting from that child) and update the parent's longest chain by considering this value plus $1$ (to include the parent itself in the chain).

When combining chains, we take the two longest chains from different child nodes of a given parent. These two chains represent the longest valid paths starting from two distinct child nodes. By combining these two chains (one from each child) with the parent node, we effectively create a new path where the parent node is in the middle, and the two chains extend in different directions from it. The sum of these two chains plus $1$ (for the parent node) gives the overall length of the longest path that can pass through the parent node.

Ultimately, we return the length of the longest valid path by using this process to resolve dependencies between nodes and efficiently calculate the result.

Before moving to the actual algorithm, let’s first understand how the parent array is visualized as an undirected tree. This will help us correctly understand and find the longest paths in the tree without distinct characters.