# Longest Path With Different Adjacent Characters
**Difficulty:** HARD
[External](https://leetcode.com/problems/longest-path-with-different-adjacent-characters)
Canonical: https://scaleengineer.com/dsa/problems/longest-path-with-different-adjacent-characters
**Algorithms:** [Depth-First Search](https://scaleengineer.com/algorithms/depth-first-search), [Topological Sort](https://scaleengineer.com/algorithms/topological-sort)
**Data structures:** Array, String, Tree, Graph
**Companies:** [Target](https://scaleengineer.com/companies/target), [Hudson River Trading](https://scaleengineer.com/companies/hudson-river-trading)
---
## Problem
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:**

![](https://assets.glich.co/dsa/longest-path-with-different-adjacent-characters/image0.png) 

**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:**

![](https://assets.glich.co/dsa/longest-path-with-different-adjacent-characters/image1.png) 

**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 <= 105`
* `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
## Brute Force: DFS from Each Node
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'.
**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).
**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.
### Explanation
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.

```java
import java.util.*;

class Solution {
    private List<Integer>[] adj;
    private String s;
    private int n;

    public int longestPath(int[] parent, String s) {
        this.n = parent.length;
        this.s = s;
        this.adj = new ArrayList[n];
        for (int i = 0; i < n; i++) {
            adj[i] = new ArrayList<>();
        }
        for (int i = 1; i < n; i++) {
            adj[parent[i]].add(i);
            adj[i].add(parent[i]);
        }

        int maxLength = 0;
        if (n > 0) {
            maxLength = 1;
        }

        for (int i = 0; i < n; i++) {
            maxLength = Math.max(maxLength, calculatePathFromNode(i));
        }
        return maxLength;
    }

    private int calculatePathFromNode(int u) {
        List<Integer> armLengths = new ArrayList<>();
        for (int v : adj[u]) {
            // We only need to traverse in one direction to avoid cycles in our helper
            // but the main loop handles all nodes as peaks, so we need full adjacency.
            // To simplify, we can pass parent to findArmLength.
            if (s.charAt(u) != s.charAt(v)) {
                armLengths.add(findArmLength(v, u));
            }
        }
        
        Collections.sort(armLengths, Collections.reverseOrder());
        
        int max1 = armLengths.isEmpty() ? 0 : armLengths.get(0);
        int max2 = armLengths.size() < 2 ? 0 : armLengths.get(1);
        
        return 1 + max1 + max2;
    }

    private int findArmLength(int u, int p) {
        int maxChildArm = 0;
        for (int v : adj[u]) {
            if (v == p) continue;
            if (s.charAt(u) != s.charAt(v)) {
                maxChildArm = Math.max(maxChildArm, findArmLength(v, u));
            }
        }
        return 1 + maxChildArm;
    }
}
```
### 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.

## Optimal Approach: Single DFS Traversal
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.
**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).
**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.
### Explanation
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`:
1. It calculates and returns the length of the longest valid path that starts at `u` and goes downwards into one of its subtrees.
2. 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.

```java
import java.util.*;

class Solution {
    private List<Integer>[] adj;
    private String s;
    private int maxLength;

    public int longestPath(int[] parent, String s) {
        int n = parent.length;
        if (n <= 1) {
            return n;
        }
        this.s = s;
        this.adj = new ArrayList[n];
        for (int i = 0; i < n; i++) {
            adj[i] = new ArrayList<>();
        }
        for (int i = 1; i < n; i++) {
            adj[parent[i]].add(i);
        }

        maxLength = 1;
        dfs(0);
        return maxLength;
    }

    private int dfs(int u) {
        // longest and secondLongest store the length of the longest and second-longest
        // paths starting from a child of u and going down.
        int longest = 0;
        int secondLongest = 0;

        for (int v : adj[u]) {
            int childPathLength = dfs(v);
            
            // If child and parent have different characters, we can extend the path
            if (s.charAt(u) != s.charAt(v)) {
                if (childPathLength > longest) {
                    secondLongest = longest;
                    longest = childPathLength;
                } else if (childPathLength > secondLongest) {
                    secondLongest = childPathLength;
                }
            }
        }

        // Update the global maxLength with the path that "bends" at the current node u.
        // This path is formed by node u and its two longest downward paths.
        maxLength = Math.max(maxLength, 1 + longest + secondLongest);

        // Return the length of the longest path starting at u and going downwards.
        // This is for the parent of u to use.
        return 1 + longest;
    }
}
```
### 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.

# Solutions
### Java

```java
class 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 ; } }
```

### CPP

```cpp
class 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 ; } };
```

### Python

```python
class 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
```