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.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.
C++
Java
Python
C#
JavaScript
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.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n^2) in this version due to lack of adjacency list optimization.
Space Complexity: O(n) related to queue usage.
| 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. |
Longest Path With Different Adjacent Characters : (Microsoft) | Explanation ➕ Live Coding • codestorywithMIK • 7,503 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