Longest Path With Different Adjacent Characters

Share

Find longest path in a tree where adjacent nodes have different characters.

Example 1
Input: parent=[-1,0,0,1,1,2], s="abacbe" → Output: 3
Example 2
Input: parent=[-1,0,0,0], s="aabc" → Output: 3

Solution Approach

Build tree, DFS from each node tracking two longest paths to children with different chars.

  • Build adjacency list from parent array
  • DFS: for each node collect top 2 longest child paths (with different char)
  • Path through this node = top1 + top2 + 1
  • Update global max
  • Return longest single path from node
Java
public int longestPath(int[] parent, String s) {
    int n = parent.length;
    List<List<Integer>> children = new ArrayList<>();
    for (int i = 0; i < n; i++) children.add(new ArrayList<>());
    for (int i = 1; i < n; i++) children.get(parent[i]).add(i);
    int[] res = {1};
    dfs(0, children, s, res);
    return res[0];
}
private int dfs(int node, List<List<Integer>> children, String s, int[] res) {
    int top1 = 0, top2 = 0;
    for (int child : children.get(node)) {
        int childLen = dfs(child, children, s, res);
        if (s.charAt(child) == s.charAt(node)) continue;
        if (childLen > top1) { top2 = top1; top1 = childLen; }
        else if (childLen > top2) top2 = childLen;
    }
    res[0] = Math.max(res[0], top1 + top2 + 1);
    return top1 + 1;
}
  • Time Complexity: O(n)
  • Space Complexity: O(n)