DSA problem

Longest Path With Different Adjacent Characters

HardDepth First Search (DFS)Pattern: Depth First Search (DFS)top600AmazonGoogleMetaMicrosoftBloomberg

You are given a tree (i.e., a connected, undirected graph that has no cycles) rooted at node 0 consisting of n nodes numbered from 0 to n - 1. The tree is represented by a 0-indexed array parent of size n, where parent[i] is the parent of node i. Since node 0 is the root, parent[0] == -1. You are also given a string s of length n, where s[i] is the character assigned to node i.

Return the length of the longest path in the tree such that no pair of adjacent nodes on the path have the same character assigned to them. A path is a sequence of distinct nodes where every two consecutive nodes share an edge in the tree. The length of a path is the number of nodes in it, so a single node forms a path of length 1.

A first instinct is to try every pair of nodes and check the simple path between them, but that is O(n^3) and far too slow. The key observation is that any valid path in a tree, when "uncurled", has a single highest node — its lowest common ancestor — and consists of two downward chains hanging off that LCA. So if we fix every node u as a candidate LCA, the best path through u is the sum of the two longest "different-character" downward chains starting at u, plus the node u itself.

This leads to a classic tree DP. Run a postorder DFS. For each node u, compute down(u) = the longest chain starting at u and going strictly downward. To do that, look at every child c whose character differs from u's, and take 1 + down(c). While iterating those children, track the top two such values; the answer through u is then 1 + top1 + top2 (using 0 if a slot has no qualifying child). A global variable records the maximum across all nodes. The total work is O(n) time and O(n) space for the recursion / adjacency list.

Examples

Example 1

Input: parent = [-1,0,0,1,1,2], s = "abacbe"

Output: 3

Explanation: The longest path where no two adjacent nodes share a character is 0 -> 1 -> 3, with characters a -> b -> c. It has 3 nodes.

Example 2

Input: parent = [-1,0,0,0], s = "aabc"

Output: 3

Explanation: The path 2 -> 0 -> 3 has characters b -> a -> c (all different on adjacent edges) and visits 3 nodes.

Example 3

Input: parent = [-1,0,1], s = "aba"

Output: 3

Explanation: The path 0 -> 1 -> 2 has characters a -> b -> a, which differ on every adjacent pair, so the answer is 3.

Constraints

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

3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.

treegraphdfsdynamic-programmingtree-dp

Browse all DSA problems