Find longest path in a tree where adjacent nodes have different characters.
Input: parent=[-1,0,0,1,1,2], s="abacbe" → Output: 3
Input: parent=[-1,0,0,0], s="aabc" → Output: 3
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
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)