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.
Example 1:
Input: parent = [-1,0,0,1,1,2], s = "abacbe" Output: 3 Explanation: The longest path where each two adjacent nodes have different characters in the tree is the path: 0 -> 1 -> 3. The length of this path is 3, so 3 is returned. It can be proven that there is no longer path that satisfies the conditions.
Example 2:
Input: parent = [-1,0,0,0], s = "aabc" Output: 3 Explanation: The longest path where each two adjacent nodes have different characters is the path: 2 -> 0 -> 3. The length of this path is 3, so 3 is returned.
Constraints:
n == parent.length == s.length1 <= n <= 1050 <= parent[i] <= n - 1 for all i >= 1parent[0] == -1parent represents a valid tree.s consists of only lowercase English letters.Problem Overview: You are given a tree with n nodes where parent[i] represents the parent of node i. Each node has a character from string s. The goal is to find the length of the longest path such that every pair of adjacent nodes in the path has different characters.
Approach 1: DFS with Recursion (Tree DP) (Time: O(n), Space: O(n))
This approach treats the tree as a graph and performs a depth-first traversal starting from the root. For each node, compute the longest valid chain that extends downward through its children while ensuring adjacent characters differ. During DFS, track the two longest child paths whose characters are different from the current node. Combining these two paths through the current node forms a candidate for the global longest path.
The key insight: the answer may pass through a node by joining two valid child branches. Maintain a global maximum while DFS returns the best single branch length to its parent. This is essentially a tree dynamic programming pattern using Depth-First Search on a tree. Each edge is processed once, giving O(n) time and O(n) recursion stack space.
Approach 2: Iterative BFS with Topological Processing (Time: O(n), Space: O(n))
This method processes the tree from leaves upward using a queue, similar to topological ordering. First build an adjacency list and compute the number of children for each node. Start with leaf nodes and propagate their longest valid path lengths toward their parents. For every node, keep track of the two longest valid chains received from children whose characters differ from the parent.
When a node finishes processing all children, combine its two best chains to update the global answer. Then push the computed best chain upward to its parent. This avoids recursion and works well when stack depth could be large. The technique resembles a mix of graph traversal and topological sort over a tree structure.
Recommended for interviews: The DFS recursive solution is what most interviewers expect. It directly models the problem as tree dynamic programming and is easy to reason about once you track the two longest valid child paths. The BFS/topological approach demonstrates deeper understanding of tree processing without recursion, which can be useful when discussing scalability or iterative alternatives.
This approach uses Depth First Search (DFS) to explore the tree and find the longest path with different adjacent characters. The idea is to recursively explore each node, keeping track of the longest path encountered. As you traverse, ensure that any subsequent node is only considered in the path if it has a different character from its parent.
The code defines a DFS function that explores each node's children, calculates the longest path from its children nodes that have distinct characters compared to the node. It accumulates the longest paths and returns the overall result.
Time Complexity: O(n).
Space Complexity: O(n) due to the storage of the children array.
Instead of using recursion, consider using an iterative Breadth First Search (BFS) approach. In this scenario, you explore each node level by level, maintaining a similar mechanism for avoiding paths with identical adjacent characters.
This approach generally requires additional bookkeeping to manage the nodes and their path lengths, but it can be beneficial in scenarios where recursion depth potential is problematic or not desired.
This implementation uses a queue-based BFS approach instead of recursion. Each node and its path length are enqueued, and the traversal occurs iteratively. As children are explored, they are enqueued only if their character differs from their parent.
Time Complexity: O(n^2) in this version due to lack of adjacency list optimization.
Space Complexity: O(n) related to queue usage.
First, we construct an adjacency list g based on the array parent, where g[i] represents all child nodes of node i.
Then we start DFS from the root node. For each node i, we traverse each child node j in g[i]. If s[i] neq s[j], then we can start from node i, pass through node j, and reach a leaf node. The length of this path is x = 1 + dfs(j). We use mx to record the longest path length starting from node i. At the same time, we update the answer ans = max(ans, mx + x) during the traversal process.
Finally, we return ans + 1.
The time complexity is O(n), and the space complexity is O(n), where n is the number of nodes.
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| DFS with Recursion | Time Complexity: O(n). |
| Iterative BFS Approach | Time Complexity: O(n^2) in this version due to lack of adjacency list optimization. |
| Tree-shaped DP | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| DFS with Recursion (Tree DP) | O(n) | O(n) | Best general solution. Clean logic for combining child paths in tree problems. |
| Iterative BFS / Topological Processing | O(n) | O(n) | Useful when avoiding recursion or handling very deep trees. |
Longest Path With Different Adjacent Characters : (Microsoft) | Explanation ➕ Live Coding • codestorywithMIK • 13,004 views views
Watch 9 more video solutions →Practice Longest Path With Different Adjacent Characters with our built-in code editor and test cases.
Practice on FleetCode