相邻字符不同的最长路径

难度: Hard

给你一棵树（即一个连通、无向、无环图），根节点是节点 0 ，这棵树由编号从 0 到 n - 1 的 n 个节点组成。用下标从 0 开始、长度为 n 的数组 parent 来表示这棵树，其中 parent[i] 是节点 i 的父节点，由于节点 0 是根节点，所以 parent[0] == -1 。

另给你一个字符串 s ，长度也是 n ，其中 s[i] 表示分配给节点 i 的字符。

请你找出路径上任意一对相邻节点都没有分配到相同字符的 最长路径 ，并返回该路径的长度。

示例 1：

输入：parent = [-1,0,0,1,1,2], s = "abacbe"
输出：3
解释：任意一对相邻节点字符都不同的最长路径是：0 -> 1 -> 3 。该路径的长度是 3 ，所以返回 3 。
可以证明不存在满足上述条件且比 3 更长的路径。

示例 2：

输入：parent = [-1,0,0,0], s = "aabc"
输出：3
解释：任意一对相邻节点字符都不同的最长路径是：2 -> 0 -> 3 。该路径的长度为 3 ，所以返回 3 。

提示：

n == parent.length == s.length
1 <= n <= 10⁵
对所有 i >= 1 ，0 <= parent[i] <= n - 1 均成立
parent[0] == -1
parent 表示一棵有效的树
s 仅由小写英文字母组成

Submission

运行时间: 420 ms

内存: 59.2 MB

class Solution:
    def longestPath(self, parent: List[int], s: str) -> int:
        n = len(s)
        dp = [[] for _ in range(n)] 
        # construct the ajacent table for the tree. If it starts from 0, then parent[0] equals -1, but it cannot be indexed in dp list
        for i in range(1, n):
            dp[parent[i]].append(i)
        ans = 0
        def func(i, dp, s):
            max_len = 0
            sec_max_len = 0
            nonlocal ans
            for j in dp[i]:
                cur_len = func(j, dp, s) + 1
                if s[i] != s[j]:
                    if cur_len > max_len:
                        max_len, sec_max_len = cur_len, max_len
                    elif cur_len > sec_max_len:
                        sec_max_len = cur_len
            ans = max(ans, max_len + sec_max_len)
            return max_len
        func(0, dp, s)
        return ans+1

Explain

此题解采用了深度优先搜索（DFS）结合动态规划（DP）的方式来处理问题。首先，将 parent 数组转换为邻接列表 dp，以便能够从任一节点遍历其子节点。对于每个节点，通过递归函数 func 检查其所有子节点，计算从当前节点向下可达的最长路径长度。关键点在于，我们需要同时维护两个长度：max_len（当前节点到子节点的最长不重复字符路径长度）和 sec_max_len（次长路径长度）。如果当前节点和子节点的字符不同，则更新这两个长度。最后，对于每个节点，其贡献的路径长度可能是 max_len + sec_max_len（即通过当前节点连接两个最长分支）。全局变量 ans 用于在所有节点中追踪最长的路径长度。

时间复杂度: O(n)

空间复杂度: O(n)

class Solution:
    def longestPath(self, parent: List[int], s: str) -> int:
        n = len(s)
        dp = [[] for _ in range(n)]  # 构建邻接列表
        # 填充邻接列表
        for i in range(1, n):
            dp[parent[i]].append(i)
        ans = 0  # 初始化最长路径变量
        def func(i, dp, s):
            max_len = 0  # 当前节点至子节点的最长路径
            sec_max_len = 0  # 次长路径
            nonlocal ans  # 引用外层变量，以更新全局最大路径长度
            for j in dp[i]:  # 遍历子节点
                cur_len = func(j, dp, s) + 1  # 递归计算子节点的路径长度
                if s[i] != s[j]:  # 检查字符是否不同
                    if cur_len > max_len:
                        max_len, sec_max_len = cur_len, max_len
                    elif cur_len > sec_max_len:
                        sec_max_len = cur_len
            ans = max(ans, max_len + sec_max_len)  # 更新全局最大路径长度
            return max_len  # 返回当前节点的最长路径
        func(0, dp, s)  # 从根节点开始DFS
        return ans+1  # 返回包含当前节点的路径长度

Explore

在构建邻接列表的过程中，并没有直接确保父节点在子节点前被处理。邻接列表只是用来记录每个节点的子节点，而实际的处理顺序是由深度优先搜索（DFS）决定的。在DFS中，我们从根节点（通常是节点0，因为它没有父节点）开始，递归地遍历每个节点的所有子节点。这种方式自然地确保了在处理任何一个节点之前，其父节点已经被处理过了，因为子节点的处理是在递归调用中发生的。这对算法的正确性至关重要，因为我们需要先知道子节点的最长路径信息，才能计算当前节点的最长路径信息。

在递归函数func中，需要维护两个最大长度值max_len和sec_max_len是因为我们要计算经过当前节点的最长路径可能包括两条不同的分支。max_len保持当前节点到其任一子节点的最长路径，而sec_max_len则保持第二长的路径。当两个最长的分支都从当前节点出发且朝不同的方向时，通过这个节点的最长路径将是这两个分支的长度之和。如果只维护一个最大长度，则我们无法计算出经过当前节点的两个最长分支的总长度，从而可能错过最长路径的正确计算。

最终返回结果时将ans加一是因为在计算路径长度时，我们实际上是在计算路径上边的数量。例如，一个由两个节点组成的路径有一条边。因此，如果我们要计算包含节点本身在内的路径长度，需要在边的数量基础上加一。在这种情况下，ans代表的是通过某个节点连接的两个最长分支的边数，因此返回结果时加一是为了包括这个中间的节点本身，从而得到整个路径包含的节点数。

如果当前节点和子节点的字符相同，我们不会考虑这两个节点之间的路径作为不同字符的路径的一部分。在这种情况下，即使子节点的路径长度很长，它也不会被用来更新max_len或sec_max_len。这是因为题目要求是找到相邻字符不同的最长路径。因此，当字符相同时，这条路径就不被考虑在内，我们只更新来自那些与当前节点字符不同的子节点的路径长度。