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.

Solution

Method 1 – DFS with Two Longest Paths Tracking

Intuition

The longest path in a tree with the constraint that adjacent nodes have different characters can be found by DFS. For each node, we track the two longest child paths that can be extended (i.e., child character differs from parent). The answer is the maximum sum of two such paths plus one (for the current node).

Approach

Build the tree as an adjacency list from the parent array.
Define a DFS function that returns the longest path starting from a node.
For each node, recursively compute the longest child paths where the child character differs from the current node.
Track the two longest such child paths for each node.
Update the global answer as the sum of the two longest child paths plus one.
Return the longest path found.

Code

[{"language":"Java","code":"class Solution {\n    int ans = 1;\n    public int longestPath(int[] parent, String s) {\n        int n = parent.length;\n        List<Integer>[] tree = new List[n];\n        for (int i = 0; i < n; i++) tree[i] = new ArrayList<>();\n        for (int i = 1; i < n; i++) tree[parent[i]].add(i);\n        dfs(0, tree, s);\n        return ans;\n    }\n    private int dfs(int u, List<Integer>[] tree, String s) {\n        int max1 = 0, max2 = 0;\n        for (int v : tree[u]) {\n            int len = dfs(v, tree, s);\n            if (s.charAt(u) != s.charAt(v)) {\n                if (len > max1) {\n                    max2 = max1;\n                    max1 = len;\n                } else if (len > max2) {\n                    max2 = len;\n                }\n            }\n        }\n        ans = Math.max(ans, max1 + max2 + 1);\n        return max1 + 1;\n    }\n}","lang":"java","html":"<pre class=\"shiki shiki-themes github-light github-dark\" style=\"background-color:#fff;--shiki-dark-bg:#24292e;color:#24292e;--shiki-dark:#e1e4e8\" tabindex=\"0\"><code><span class=\"line\"><span style=\"color:#D73A49;--shiki-dark:#F97583\">class</span><span style=\"color:#6F42C1;--shiki-dark:#B392F0\"> Solution</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\"> {</span></span>\n<span class=\"line\"><span style=\"color:#D73A49;--shiki-dark:#F97583\">    int</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\"> ans </span><span style=\"color:#D73A49;--shiki-dark:#F97583\">=</span><span style=\"color:#005CC5;--shiki-dark:#79B8FF\"> 1</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\">;</span></span>\n<span class=\"line\"><span style=\"color:#D73A49;--shiki-dark:#F97583\">    public</span><span style=\"color:#D73A49;--shiki-dark:#F97583\"> int</span><span style=\"color:#6F42C1;--shiki-dark:#B392F0\"> longestPath</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\">(</span><span style=\"color:#D73A49;--shiki-dark:#F97583\">int</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\">[] </span><span style=\"color:#E36209;--shiki-dark:#FFAB70\">parent</span>&

Related Tags