Longest Path With Different Adjacent Characters

hard tree dp dfs

Problem

You have a tree of n nodes rooted at node 0, given as a parent array where parent[i] is the parent of node i (and parent[0] = -1), plus a string s where s[i] is the lowercase letter written on node i.

Find the longest path in the tree such that no two adjacent nodes on the path carry the same letter, and return its length counted in nodes.

Inputparent = [-1,0,0,1,1,2], s = "abacbe"

Output3

One longest path is 3 → 1 → 0 with letters c, b, a — no two neighbouring letters match, and every path of 4 or more nodes repeats a letter somewhere.

parent (comma-separated, -1 for the root)

s (one lowercase letter per node)

def longest_path(parent, s):
    n = len(parent)
    children = [[] for _ in range(n)]
    for i in range(1, n):
        children[parent[i]].append(i)
    ans = 1

    def dfs(u):
        nonlocal ans
        best1 = best2 = 0
        for v in children[u]:
            chain = dfs(v)
            if s[v] != s[u]:
                if chain > best1:
                    best1, best2 = chain, best1
                elif chain > best2:
                    best2 = chain
        ans = max(ans, best1 + best2 + 1)
        return best1 + 1

    dfs(0)
    return ans

function longestPath(parent, s) {
  const n = parent.length;
  const children = Array.from({ length: n }, () => []);
  for (let i = 1; i < n; i++) children[parent[i]].push(i);
  let ans = 1;

  function dfs(u) {
    let best1 = 0, best2 = 0;
    for (const v of children[u]) {
      const chain = dfs(v);
      if (s[v] !== s[u]) {
        if (chain > best1) { best2 = best1; best1 = chain; }
        else if (chain > best2) best2 = chain;
      }
    }
    ans = Math.max(ans, best1 + best2 + 1);
    return best1 + 1;
  }

  dfs(0);
  return ans;
}

class Solution {
    List<List<Integer>> children;
    String s;
    int ans = 1;

    public int longestPath(int[] parent, String s) {
        int n = parent.length;
        this.s = s;
        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);
        dfs(0);
        return ans;
    }

    int dfs(int u) {
        int best1 = 0, best2 = 0;
        for (int v : children.get(u)) {
            int chain = dfs(v);
            if (s.charAt(v) != s.charAt(u)) {
                if (chain > best1) { best2 = best1; best1 = chain; }
                else if (chain > best2) best2 = chain;
            }
        }
        ans = Math.max(ans, best1 + best2 + 1);
        return best1 + 1;
    }
}

class Solution {
public:
    int longestPath(vector<int>& parent, string s) {
        int n = parent.size();
        vector<vector<int>> children(n);
        for (int i = 1; i < n; i++) children[parent[i]].push_back(i);
        int ans = 1;
        function<int(int)> dfs = [&](int u) {
            int best1 = 0, best2 = 0;
            for (int v : children[u]) {
                int chain = dfs(v);
                if (s[v] != s[u]) {
                    if (chain > best1) { best2 = best1; best1 = chain; }
                    else if (chain > best2) best2 = chain;
                }
            }
            ans = max(ans, best1 + best2 + 1);
            return best1 + 1;
        };
        dfs(0);
        return ans;
    }
};

Explanation

This is the tree diameter pattern with one extra filter. Any path in a tree has a unique highest node u: the path climbs up to u through one child and descends through another. So the longest valid path equals, over all nodes, the best way to combine two downward chains that hang from different children of u — keeping only children whose letter differs from s[u].

The post-order DFS returns chain(u), the longest downward path starting at u in which adjacent letters differ. For each child v, we recurse first; if s[v] != s[u] the chain may be extended through u, so we keep the two largest such child chains as best1 and best2 (children with the same letter are simply ignored). Then chain(u) = best1 + 1, and the best path bending at u has best1 + best2 + 1 nodes — that candidate updates the global answer.

Walk through parent = [-1,0,0,1,1,2], s = "abacbe". Leaves 3 ('c'), 4 ('b') and 5 ('e') each get chain 1. At node 1 ('b'), child 3 ('c') differs and contributes chain 1, but child 4 ('b') repeats the letter and is skipped, so chain(1) = 2 and the candidate is 2. Node 2 ('a') accepts child 5 ('e') for chain 2.

At the root 0 ('a'), child 1 contributes chain 2 while child 2 ('a') is skipped because it matches. That gives best1 = 2, best2 = 0, candidate 2 + 0 + 1 = 3 — the answer, realised by the path 3 → 1 → 0 with letters c, b, a.

Note the answer is at least 1 (a single node is a valid path), which is why ans starts at 1. Skipping equal-letter children is safe: any valid path entering u from such a child would put two equal letters next to each other.

The DFS visits every node once and examines every edge once when scanning children, so the time is O(n); the children lists and the recursion stack take O(n) space.

Time: O(n) Space: O(n)