Get started

Longest Path With Different Adjacent Characters — Hard Problem & Solution

A tree has n nodes numbered 0 to n - 1 and is rooted at node 0.

Problem statement

A tree has n nodes numbered 0 to n - 1 and is rooted at node 0. It is given by the array parent, where parent[i] is the parent of node i; the root has parent[0] == -1. Node i is labelled with the character s[i].

A path is a sequence of distinct nodes in which each consecutive pair is joined by a tree edge (it may go up and then down). Return the number of nodes on the longest path in which no two adjacent nodes carry the same character.

Example 1

Input: parent = [-1,0,0,1,1,2], s = "kairok"
Output: 5
Explanation: Every edge joins different letters, so the longest path 3 → 1 → 0 → 2 → 5 counts.

Example 2

Input: parent = [-1,0,1,2], s = "abba"
Output: 2
Explanation: The edge between nodes 1 and 2 joins two `b`s, splitting the chain.

Example 3

Input: parent = [-1], s = "z"
Output: 1

Constraints

  • n == parent.length == s.length
  • 1 <= n <= 10^5
  • 0 <= parent[i] <= n - 1 for all i >= 1
  • parent[0] == -1
  • parent represents a valid tree
  • s consists of only lowercase English letters

How to solve Longest Path With Different Adjacent Characters

This is a tree-diameter computation where an edge counts only if its endpoints differ. Every path has a unique highest node, where it joins at most two downward chains.

Approach

  1. Build child lists from parent and produce a BFS order from the root.
  2. Walk the order backwards (children before parents). For node u, look at children v with s[v] != s[u] and keep the two largest values of chain[v].
  3. Set chain[u] = 1 + top1, and update the answer with 1 + top1 + top2.
  4. Return the best value found (at least 1).

Why it works

Any valid path has a highest node u; the parts below u are downward chains through two different children (or fewer), each starting at a child whose letter differs from u's. The longest such chains are exactly top1 and top2, so 1 + top1 + top2 is the best path whose top is u; maximising over all u covers every path. Reverse BFS order guarantees each child's chain is final before its parent reads it.

Complexity

  • Time — O(n)
  • Space — O(n)

Pitfalls

  • A child with the same letter contributes nothing to u, but its own subtree can still hold the answer — never skip visiting it.
  • parent[i] < i is not guaranteed, so you cannot simply loop indices downward; use a real traversal order.
  • Recursion depth can reach 10^5 on a chain — prefer an iterative order.

Reference solution

Python

from typing import List

def longestPath(parent: List[int], s: str) -> int:
    n = len(parent)
    children = [[] for _ in range(n)]
    for i in range(1, n):
        children[parent[i]].append(i)
    order = [0]
    for u in order:
        order.extend(children[u])
    chain = [1] * n
    best = 1
    for u in reversed(order):
        top1 = top2 = 0
        for v in children[u]:
            if s[v] != s[u]:
                c = chain[v]
                if c > top1:
                    top1, top2 = c, top1
                elif c > top2:
                    top2 = c
        chain[u] = 1 + top1
        if 1 + top1 + top2 > best:
            best = 1 + top1 + top2
    return best

JavaScript

var longestPath = function(parent, s) {
    var n = parent.length;
    var children = [];
    for (var i = 0; i < n; i++) children.push([]);
    for (var k = 1; k < n; k++) children[parent[k]].push(k);
    var order = [0];
    for (var h = 0; h < order.length; h++) {
        var kids = children[order[h]];
        for (var j = 0; j < kids.length; j++) order.push(kids[j]);
    }
    var chain = [];
    for (var c = 0; c < n; c++) chain.push(1);
    var best = 1;
    for (var t = n - 1; t >= 0; t--) {
        var u = order[t], top1 = 0, top2 = 0;
        for (var q = 0; q < children[u].length; q++) {
            var v = children[u][q];
            if (s.charAt(v) === s.charAt(u)) continue;
            if (chain[v] > top1) { top2 = top1; top1 = chain[v]; }
            else if (chain[v] > top2) top2 = chain[v];
        }
        chain[u] = 1 + top1;
        if (1 + top1 + top2 > best) best = 1 + top1 + top2;
    }
    return best;
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 988 arrays problems · the whole catalogue

Learn the technique: Arrays · Strings