Longest Path With Different Adjacent Characters LeetCode solution in Java

1
class Solution {
2
  int longestPathValue = 1; // variable to store the length of the longest path
3

4
  public int longestPath(int[] parent, String s) {
5
    // create an adjacency list representation of the tree
6
    Map<Integer, List<Integer>> adj = new HashMap<>();
7
    for (int i = 1; i < parent.length; i++) {
8
      int j = parent[i];
9
      adj.putIfAbsent(j, new LinkedList<>());
10
      adj.get(j).add(i);
11
    }
12
    // call dfs on the root of the tree
13
    dfs(0, adj, s);
14
    return longestPathValue;
15
  }
16

17
  public int dfs(int node, Map<Integer, List<Integer>> adj, String s) {
18
    // if the node is a leaf node, return 1
19
    if (!adj.containsKey(node)) return 1;
20
    int max = 0, secondMax = 0;
21
    // for each neighbor of the node
22
    for (int nbrNode : adj.get(node)) {
23
      int longestPathFromNbrNode = dfs(nbrNode, adj, s);
24
      // if the characters at the current node and its neighbor are the same, ignore the neighbor
25
      if (s.charAt(node) == s.charAt(nbrNode)) continue;
26
      // update max and secondMax with the longest path from the neighbor node
27
      if (longestPathFromNbrNode > max) {
28
        secondMax = max;
29
        max = longestPathFromNbrNode;
30
      } else if (longestPathFromNbrNode > secondMax) {
31
        secondMax = longestPathFromNbrNode;
32
      }
33
    }
34
    // update longestPathValue with the longest path that includes the current node
35
    longestPathValue = Math.max(longestPathValue, max + secondMax + 1);
36
    return max + 1;
37
  }
38
}