Longest Path With Different Adjacent Characters

Hard
1536.

Longest Path With Different Adjacent Characters

Longest Path With Different Adjacent Characters is a hard coding problem on arrays, strings and depth-first search, asked in Amazon and Google interviews.

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
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} parent
 * @param {string} s
 * @return {number}
 */
var longestPath = function(parent, s) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Longest Path With Different Adjacent Characters — Solution

Longest Path With Different Adjacent Characters solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.

Longest Path With Different Adjacent Characters is a hard coding problem on arrays, strings and depth-first search, asked in Amazon and Google interviews.

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

Hints for Longest Path With Different Adjacent Characters

  1. Hint 1

    Throw away every edge whose two ends have the same letter — the answer is the longest path (diameter, counted in nodes) in what remains.

  2. Hint 2

    Root the tree at 0. For every node, compute the longest valid downward chain starting at it.

  3. Hint 3

    A best path bends at its highest node: combine that node with its two longest child chains (only children whose letter differs). Process nodes children-first, e.g. in reverse BFS order, to avoid deep recursion.

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

Java

public static 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[] order = new int[n];
    int tail = 0;
    order[tail++] = 0;
    for (int h = 0; h < tail; h++) for (int v : children.get(order[h])) order[tail++] = v;
    int[] chain = new int[n];
    int best = 1;
    for (int t = n - 1; t >= 0; t--) {
        int u = order[t], top1 = 0, top2 = 0;
        for (int v : children.get(u)) {
            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;
        best = Math.max(best, 1 + top1 + top2);
    }
    return best;
}

C++

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);
    vector<int> order;
    order.push_back(0);
    for (size_t h = 0; h < order.size(); h++) for (int v : children[order[h]]) order.push_back(v);
    vector<int> chain(n, 1);
    int best = 1;
    for (int t = n - 1; t >= 0; t--) {
        int u = order[t], top1 = 0, top2 = 0;
        for (int v : children[u]) {
            if (s[v] == s[u]) continue;
            if (chain[v] > top1) { top2 = top1; top1 = chain[v]; }
            else if (chain[v] > top2) top2 = chain[v];
        }
        chain[u] = 1 + top1;
        best = max(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#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Strings