Longest Path With Different Adjacent Characters

Hard

#2046Time: O(N^2), where N is the number of nodes. The main loop iterates `N` times. Inside the loop, for each node `i`, we call `findArmLength` on its neighbors. In the worst case (e.g., a star graph), `findArmLength` might traverse a significant portion of the tree, leading to `O(N)` work for each of the `N` starting nodes.Space: O(N), where N is the number of nodes. The space is required for the adjacency list (`O(N)`) and the recursion stack for the DFS (`O(N)` in the worst case of a skewed tree).2 companies

Algorithms

Depth-First Search Topological Sort

Data structures

Array String Tree Graph

Companies

Target Hudson River Trading

Prompt

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.length
1 <= n <= 10⁵
0 <= parent[i] <= n - 1 for all i >= 1
parent[0] == -1
parent represents a valid tree.
s consists of only lowercase English letters.

Approaches

2 approaches with complexity analysis and trade-offs.

This approach iterates through every node in the tree, considering each one as the potential 'peak' or 'bend' of the longest path. For each node, it calculates the longest possible path that has this node as its highest point by running a separate Depth First Search (DFS) for each of its 'arms'.

Algorithm

Build an adjacency list representation of the tree from the parent array.
Initialize a global variable maxLength = 1.
Iterate through each node i from 0 to n-1, considering it as the potential 'peak' of the longest path.
For each node i:
- Create a list to store the lengths of valid 'arms' starting from i.
- For each neighbor j of i:
  - If s.charAt(i) != s.charAt(j), it's a valid start for an arm. Calculate the length of this arm by calling a helper DFS function, findArmLength(j, i), which finds the longest valid path starting from j and moving away from i. The total arm length is 1 + findArmLength(j, i).
  - Add this length to the list of arms.
- Sort the arm lengths in descending order.
- The longest path with i as the peak is formed by i itself plus its two longest arms. Its length is 1 + max1 + max2, where max1 and max2 are the two largest arm lengths (or 0 if not present).
- Update maxLength = max(maxLength, 1 + max1 + max2).
After checking all nodes as potential peaks, maxLength will hold the answer.

Walkthrough

The main idea is to test every node as the root of the longest path. We first build an adjacency list for the tree. Then, we iterate through each node i from 0 to n-1. For each node i, we treat it as the highest point of a potential path. A path passing through i consists of i itself and one or two 'arms' extending into different subtrees. An arm can only extend to a neighbor j if s.charAt(i) != s.charAt(j).

To find the length of these arms, we run a helper DFS function, findArmLength(u, p), which calculates the length of the longest valid path starting at node u and moving away from its parent p. For each node i, we gather the lengths of the arms extending to its valid neighbors (1 + findArmLength(neighbor, i)). We then find the two longest arms, max1 and max2. The longest path centered at i has length 1 + max1 + max2. We update our global maximum with this value. The final result is the global maximum found after checking all nodes.

1import java.util.*;2 3class Solution {4    private List<Integer>[] adj;5    private String s;6    private int n;7 8    public int longestPath(int[] parent, String s) {9        this.n = parent.length;10        this.s = s;11        this.adj = new ArrayList[n];12        for (int i = 0; i < n; i++) {13            adj[i] = new ArrayList<>();14        }15        for (int i = 1; i < n; i++) {16            adj[parent[i]].add(i);17            adj[i].add(parent[i]);18        }19 20        int maxLength = 0;21        if (n > 0) {22            maxLength = 1;23        }24 25        for (int i = 0; i < n; i++) {26            maxLength = Math.max(maxLength, calculatePathFromNode(i));27        }28        return maxLength;29    }30 31    private int calculatePathFromNode(int u) {32        List<Integer> armLengths = new ArrayList<>();33        for (int v : adj[u]) {34            // We only need to traverse in one direction to avoid cycles in our helper35            // but the main loop handles all nodes as peaks, so we need full adjacency.36            // To simplify, we can pass parent to findArmLength.37            if (s.charAt(u) != s.charAt(v)) {38                armLengths.add(findArmLength(v, u));39            }40        }41        42        Collections.sort(armLengths, Collections.reverseOrder());43        44        int max1 = armLengths.isEmpty() ? 0 : armLengths.get(0);45        int max2 = armLengths.size() < 2 ? 0 : armLengths.get(1);46        47        return 1 + max1 + max2;48    }49 50    private int findArmLength(int u, int p) {51        int maxChildArm = 0;52        for (int v : adj[u]) {53            if (v == p) continue;54            if (s.charAt(u) != s.charAt(v)) {55                maxChildArm = Math.max(maxChildArm, findArmLength(v, u));56            }57        }58        return 1 + maxChildArm;59    }60}

Complexity

Time

O(N^2), where N is the number of nodes. The main loop iterates `N` times. Inside the loop, for each node `i`, we call `findArmLength` on its neighbors. In the worst case (e.g., a star graph), `findArmLength` might traverse a significant portion of the tree, leading to `O(N)` work for each of the `N` starting nodes.

Space

O(N), where N is the number of nodes. The space is required for the adjacency list (`O(N)`) and the recursion stack for the DFS (`O(N)` in the worst case of a skewed tree).

Trade-offs

Pros

Conceptually straightforward as it breaks the problem down into smaller, repeated subproblems.
Correctly solves the problem for any valid tree structure.

Cons

Highly inefficient due to redundant computations. The findArmLength function is called multiple times for the same nodes and subtrees.
The O(N^2) time complexity will cause a 'Time Limit Exceeded' (TLE) error on large test cases.

This optimal approach solves the problem in a single pass using a Depth First Search (DFS). It uses a post-order traversal strategy where each node, after visiting all its children, calculates two key pieces of information: the longest path that can be formed by 'bending' at the current node, and the longest path that can be extended upwards to its parent. This avoids redundant calculations and achieves linear time complexity.

Algorithm

First, build an adjacency list representation of the tree from the parent array. A directed graph from parent to child is sufficient.
Initialize a global variable maxLength = 1 to keep track of the longest path found so far.
Define a recursive DFS function, dfs(u), that will traverse the tree and return the length of the longest valid path starting at node u and extending downwards.
Start the traversal by calling dfs(0) on the root node.
Inside dfs(u):
- Initialize longest = 0 and secondLongest = 0. These will store the lengths of the two longest downward paths from the children of u.
- For each child v of u:
  - Recursively call dfs(v) to get childPathLength, the longest downward path starting from v.
  - If s.charAt(u) != s.charAt(v), the path from v can be extended to u. Update longest and secondLongest with childPathLength.
- After iterating through all children, a potential longest path is one that 'bends' at node u. Its length is 1 + longest + secondLongest. Update the global maxLength with this value: maxLength = max(maxLength, 1 + longest + secondLongest).
- The function dfs(u) must return the length of the single longest downward path to its parent. This value is 1 + longest.
After the initial dfs(0) call completes, maxLength will hold the final answer.

Walkthrough

The core idea is to use a single DFS traversal to compute the answer. We first build an adjacency list from the parent array. We maintain a global variable, maxLength, initialized to 1, to store the length of the longest path found so far.

The DFS function, say dfs(u), performs two tasks for each node u:

It calculates and returns the length of the longest valid path that starts at u and goes downwards into one of its subtrees.
It calculates the length of the longest valid path that 'bends' at u and updates the global maxLength if this path is longer.

For a node u, the dfs(u) function works as follows: It recursively calls dfs for all children of u. It keeps track of the two longest downward paths from its children, let's call them longest and secondLongest. For each child v, it gets the result of dfs(v). If s.charAt(u) is different from s.charAt(v), this path can be extended to u, and its length is used to update longest and secondLongest. After checking all children, the longest path that 'bends' at u has a length of 1 + longest + secondLongest. We update maxLength with this value. Finally, dfs(u) returns 1 + longest to its parent, which is the information the parent needs for its own calculation.

1import java.util.*;2 3class Solution {4    private List<Integer>[] adj;5    private String s;6    private int maxLength;7 8    public int longestPath(int[] parent, String s) {9        int n = parent.length;10        if (n <= 1) {11            return n;12        }13        this.s = s;14        this.adj = new ArrayList[n];15        for (int i = 0; i < n; i++) {16            adj[i] = new ArrayList<>();17        }18        for (int i = 1; i < n; i++) {19            adj[parent[i]].add(i);20        }21 22        maxLength = 1;23        dfs(0);24        return maxLength;25    }26 27    private int dfs(int u) {28        // longest and secondLongest store the length of the longest and second-longest29        // paths starting from a child of u and going down.30        int longest = 0;31        int secondLongest = 0;32 33        for (int v : adj[u]) {34            int childPathLength = dfs(v);35            36            // If child and parent have different characters, we can extend the path37            if (s.charAt(u) != s.charAt(v)) {38                if (childPathLength > longest) {39                    secondLongest = longest;40                    longest = childPathLength;41                } else if (childPathLength > secondLongest) {42                    secondLongest = childPathLength;43                }44            }45        }46 47        // Update the global maxLength with the path that "bends" at the current node u.48        // This path is formed by node u and its two longest downward paths.49        maxLength = Math.max(maxLength, 1 + longest + secondLongest);50 51        // Return the length of the longest path starting at u and going downwards.52        // This is for the parent of u to use.53        return 1 + longest;54    }55}

Complexity

Time

O(N), where N is the number of nodes. Each node in the tree is visited exactly once during the DFS traversal. Building the adjacency list also takes `O(N)` time.

Space

O(N), where N is the number of nodes. This space is used for building the adjacency list (`O(N)`) and for the recursion stack of the DFS (`O(N)` in the worst-case of a skewed tree, `O(log N)` for a balanced tree).

Trade-offs

Pros

Extremely efficient with linear time complexity, making it suitable for large inputs.
Solves the problem in a single pass over the tree, avoiding any redundant work.
Elegant solution that effectively uses the properties of DFS and post-order traversal.

Cons

The recursive logic, which involves both updating a global maximum and returning a value for the parent, can be slightly more complex to reason about compared to a simple traversal.

Solutions

Solution

1class Solution { private List < Integer >[] g ; private String s ; private int ans ; public int longestPath ( int [] parent , String s ) { int n = parent . length ; g = new List [ n ]; this . s = s ; Arrays . setAll ( g , k -> new ArrayList <>()); for ( int i = 1 ; i < n ; ++ i ) { g [ parent [ i ]]. add ( i ); } dfs ( 0 ); return ans + 1 ; } private int dfs ( int i ) { int mx = 0 ; for ( int j : g [ i ]) { int x = dfs ( j ) + 1 ; if ( s . charAt ( i ) != s . charAt ( j )) { ans = Math . max ( ans , mx + x ); mx = Math . max ( mx , x ); } } return mx ; } }

1class Solution { public: int longestPath ( vector < int >& parent , string s ) { int n = parent . size (); vector < int > g [ n ]; for ( int i = 1 ; i < n ; ++ i ) { g [ parent [ i ]]. push_back ( i ); } int ans = 0 ; function < int ( int ) > dfs = [ & ]( int i ) -> int { int mx = 0 ; for ( int j : g [ i ]) { int x = dfs ( j ) + 1 ; if ( s [ i ] != s [ j ]) { ans = max ( ans , mx + x ); mx = max ( mx , x ); } } return mx ; }; dfs ( 0 ); return ans + 1 ; } };

1class Solution : def longestPath ( self , parent : List [ int ], s : str ) -> int : def dfs ( i : int ) -> int : mx = 0 nonlocal ans for j in g [ i ]: x = dfs ( j ) + 1 if s [ i ] != s [ j ]: ans = max ( ans , mx + x ) mx = max ( mx , x ) return mx g = defaultdict ( list ) for i in range ( 1 , len ( parent )): g [ parent [ i ]]. append ( i ) ans = 0 dfs ( 0 ) return ans + 1

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem