Sponsored
Sponsored
This approach uses Depth First Search (DFS) to explore the tree and find the longest path with different adjacent characters. The idea is to recursively explore each node, keeping track of the longest path encountered. As you traverse, ensure that any subsequent node is only considered in the path if it has a different character from its parent.
Time Complexity: O(n).
Space Complexity: O(n) due to the storage of the children array.
1import java.util.*;
2
3class Solution {
4 public int longestPath(int[] parent, String s) {
5 int n = parent.length;
6 List<Integer>[] children = new ArrayList[n];
7 for (int i = 0; i < n; i++) {
8 children[i] = new ArrayList<>();
9 }
10 for (int i = 1; i < n; i++) {
11 children[parent[i]].add(i);
12 }
13 int[] max_length = new int[1];
14 dfs(0, s, children, max_length);
15 return max_length[0];
16 }
17
18 private int dfs(int node, String s, List<Integer>[] children, int[] max_length) {
19 int firstLongest = 0, secondLongest = 0;
20 for (int child : children[node]) {
21 int pathLength = dfs(child, s, children, max_length);
22 if (s.charAt(node) != s.charAt(child)) {
23 if (pathLength > firstLongest) {
24 secondLongest = firstLongest;
25 firstLongest = pathLength;
26 } else if (pathLength > secondLongest) {
27 secondLongest = pathLength;
28 }
29 }
30 }
31 max_length[0] = Math.max(max_length[0], firstLongest + secondLongest + 1);
32 return firstLongest + 1;
33 }
34}In this solution, the DFS algorithm is applied to find the longest path by dynamically building a list of children nodes. The longest path is determined by calculating non-overlapping longest paths for each node recursively.
Instead of using recursion, consider using an iterative Breadth First Search (BFS) approach. In this scenario, you explore each node level by level, maintaining a similar mechanism for avoiding paths with identical adjacent characters.
This approach generally requires additional bookkeeping to manage the nodes and their path lengths, but it can be beneficial in scenarios where recursion depth potential is problematic or not desired.
Time Complexity: O(n^2) in this version due to lack of adjacency list optimization.
Space Complexity: O(n) related to queue usage.
In this Java solution, BFS iteratively explores nodes. The queue tracks the current path length, ensuring only paths with different adjacent characters are considered, supporting scalability without recursion limits.