LC 2246. 相邻字符不同的最长路径

题目描述

这是 LeetCode 上的 2246. 相邻字符不同的最长路径 ，难度为困难。

给你一棵树（即一个连通、无向、无环图），根节点是节点 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^5$
对所有 i >= 1，0 <= parent[i] <= n - 1 均成立
$parent[0] = -1$
parent 表示一棵有效的树
s 仅由小写英文字母组成

DFS

起始先用 parent 进行建图，随后设计 DFS 函数来求解每个节点“往下”的最长路径：将当前节点 cur 作为传入参数，返回以节点“往下”的最长路径。

这是一个由子节点最长路径推导父节点最长路径的「自下而上」的推导过程。

先来关注该 DFS 的功能本身：

假设当前处理到的节点为 u，将要访问到的节点为 j。递归调用 DFS 函数拿到以节点 j 为根节点时的“往下”最大路径 t，并执行如下处理流程：

若节点 j 和节点 u 对应字符相同，说明将节点 j 拼接在节点 u 后面并非合法路径，跳过处理
否则使用 t 来更新以当前节点 u 为根时，最大的“往下”子路径 res（该值初始值为 0）

当处理完节点 u 的所有子节点，我们 res + 1 即是函数返回值（含义为在合法的最长路径本身拼接节点 u）。

再来关注 DFS 过程中，如何计算问题答案：

在 DFS 函数中，我们递归处理了所有节点，而在真实最长路径在原树中的最高点，自然也是被处理到的。

这引导我们可以在单次递归，处理当前节点时，使用变量 l1 和 l2 分别记录当前节点的「最大子路径」和「次大子路径」。

在处理完当前节点后，1 + l1 + l2 即是以当前节点作为路径最高点时的最大路径长度（含义为在合法「最大子路径」和「次大子路径」基础上拼接当前节点），用其更新全局变量 ans。

代码：

class Solution {
    int N = 100010, M = N, idx = 0, ans = 1;
    int[] he = new int[N], e = new int[M], ne = new int[M];
    char[] cs;
    void add(int a, int b) {
        e[idx] = b;
        ne[idx] = he[a];
        he[a] = idx++;
    }
    public int longestPath(int[] parent, String s) {
        Arrays.fill(he, -1);
        for (int i = 1; i < parent.length; i++) add(parent[i], i);
        cs = s.toCharArray();
        dfs(0);
        return ans;
    }
    int dfs(int u) {
        int res = 0;
        int l1 = 0, l2 = 0;
        for (int i = he[u]; i != -1; i = ne[i]) {
            int j = e[i];
            int t = dfs(j);
            if (cs[u] == cs[j]) continue;
            if (t > l1) {
                l2 = l1; l1 = t;
            } else if (t > l2) {
                l2 = t;
            }
            res = Math.max(res, t);
            ans = Math.max(ans, 1 + l1 + l2);
        }
        return res + 1;
    }
}

时间复杂度：$O(n)$
空间复杂度：$O(n)$

树形 DP

自然也是能够使用「树形 DP」思路来做。

只不过对于「定根树形 DP」来说，往往一遍 DFS 就能实现 $O(n)$ 做法。例如 124. 二叉树中的最大路径和。

而「换根树形 DP」则只能通过对“方向”的拆分，用两遍 DFS 来进行求解。例如 310. 最小高度树和 834. 树中距离之和。

在「定根树形 DP」题目中采用「换根树形 DP」做法，无论是从执行流程还是编码来说，都稍显“多余”（毕竟一次 DFS 就能以「最佳路径的最高点必然能够被处理」来得证答案的正确性），但在验证大家是否真正掌握「树形 DP」精髓来说，却有极大意义。

代码：

class Solution {
    int N = 100010, M = N, idx = 0;
    int[] he = new int[N], e = new int[M], ne = new int[M];
    char[] cs;
    int[] f1 = new int[N], f2 = new int[N], g = new int[N], p = new int[N];
    void add(int a, int b) {
        e[idx] = b;
        ne[idx] = he[a];
        he[a] = idx++;
    }
    public int longestPath(int[] parent, String s) {
        Arrays.fill(he, -1);
        for (int i = 1; i < parent.length; i++) add(parent[i], i);
        cs = s.toCharArray();
        dfs1(0);
        dfs2(0);
        int ans = 1;
        int[] temp = new int[3];
        for (int i = 0; i < parent.length; i++) {
            temp[0] = f1[i]; temp[1] = f2[i]; temp[2] = g[i];
            Arrays.sort(temp);
            ans = Math.max(ans, 1 + temp[1] + temp[2]);
        }
        return ans;
    }
    int dfs1(int u) {
        int ans = 0;
        for (int i = he[u]; i != -1; i = ne[i]) {
            int j = e[i];
            int t = dfs1(j);
            if (cs[u] == cs[j]) continue;
            if (t > f1[u]) {
                f2[u] = f1[u]; f1[u] = t;
                p[u] = j;
            } else if (t > f2[u]) {
                f2[u] = t;
            }
            ans = Math.max(ans, t);
        }
        return ans + 1;
    }
    void dfs2(int u) {
        for (int i = he[u]; i != -1; i = ne[i]) {
            int j = e[i];
            if (cs[u] != cs[j]) {
                // 往上再往上
                g[j] = g[u] + 1;
                // 往上再往下（根据 u 的往下最大路径是否由 j 参与决定使用 最大值 还是 次大值）
                if (p[u] != j) g[j] = Math.max(g[j], 1 + f1[u]);
                else g[j] = Math.max(g[j], 1 + f2[u]);
            }
            dfs2(j);
        }
    }
}

时间复杂度：常数较大的 $O(n)$。相比于一次 DFS 的做法来说，额外多了一次 DFS，以及构建答案时对定长数组的排序操作
空间复杂度：$O(n)$

最后

这是我们「刷穿 LeetCode」系列文章的第 No.2346 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先把所有不带锁的题目刷完。

在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。

为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：https://github.com/SharingSource/LogicStack-LeetCode 。

在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。

动态规划 DFS 树形 DP 树

本博客所有文章除特别声明外，均采用 CC BY-SA 4.0 协议，转载请注明出处！

LC 543. 二叉树的直径上一篇

LC 124. 二叉树中的最大路径和下一篇