Longest Path With Different Adjacent Characters
Hard · Trees · Array · String · Tree · Depth-First Search · Graph · Topological Sort
Problem
You are given a tree of n nodes numbered 0 to n - 1, rooted at node 0, as an array parent: parent[i] is the parent of node i, and parent[0] == -1. You are also given a string s of length n, where s[i] is the character on node i.
Return the number of nodes on the longest path in which no two neighboring nodes carry the same character. A path is a sequence of distinct nodes in which each consecutive pair is joined by an edge; it may go up through a node and back down into another branch.
Examples
Input: parent = [-1,0,0,1,1,2], s = "abcbda" Output: 5
The path 4 → 1 → 0 → 2 → 5 reads d, b, a, c, a with no equal neighbors. Node 3 cannot join, because it shares b with node 1.
Input: parent = [-1,0,0], s = "aaa" Output: 1
Every edge joins two a's, so a path can only be a single node.
Input: parent = [-1,0,1,2], s = "abab" Output: 4
The letters alternate along the chain, so all four nodes form a path.
Constraints
- n == len(parent) == len(s)
- 1 <= n <= 10^5
- parent[0] == -1, and 0 = 1
- parent describes a valid tree
- s consists of lowercase English letters
Approaches
- Baseline: walk from every node — time O(n²), space O(n)
Follow-up
The same top-two-chains pass solves any "longest path in a tree where neighbors must satisfy a rule": swap the rule for "values differ by at most d" (the first use case) or "characters are equal" (the second). Why does the recursive version need care in Python, and how does the reversed breadth-first order avoid it?
Related problems
Start free on Cariara · Coding problems · System design studio
