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.
Examples#
Example 1:
1
2
3
4
5
6
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:
1
2
3
4
5
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.
Solution#
Method 1 – DFS with Two Longest Paths Tracking#
Intuition#
The longest path in a tree with the constraint that adjacent nodes have different characters can be found by DFS. For each node, we track the two longest child paths that can be extended (i.e., child character differs from parent). The answer is the maximum sum of two such paths plus one (for the current node).
Approach#
Build the tree as an adjacency list from the parent array.
Define a DFS function that returns the longest path starting from a node.
For each node, recursively compute the longest child paths where the child character differs from the current node.
Track the two longest such child paths for each node.
Update the global answer as the sum of the two longest child paths plus one.
Return the longest path found.
Code#
Java
Cpp
Go
Python
Rust
Typescript
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
int ans = 1;
public int longestPath (int [] parent, String s) {
int n = parent.length ;
List< Integer>[] tree = new List[ n] ;
for (int i = 0; i < n; i++ ) tree[ i] = new ArrayList<> ();
for (int i = 1; i < n; i++ ) tree[ parent[ i]] .add (i);
dfs(0, tree, s);
return ans;
}
private int dfs (int u, List< Integer>[] tree, String s) {
int max1 = 0, max2 = 0;
for (int v : tree[ u] ) {
int len = dfs(v, tree, s);
if (s.charAt (u) != s.charAt (v)) {
if (len > max1) {
max2 = max1;
max1 = len;
} else if (len > max2) {
max2 = len;
}
}
}
ans = Math.max (ans, max1 + max2 + 1);
return max1 + 1;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
public :
int ans = 1 ;
int longestPath (vector< int >& parent, string s) {
int n = parent.size();
vector< vector< int >> tree(n);
for (int i = 1 ; i < n; ++ i) tree[parent[i]].push_back(i);
dfs(0 , tree, s);
return ans;
}
int dfs (int u, vector< vector< int >>& tree, string& s) {
int max1 = 0 , max2 = 0 ;
for (int v : tree[u]) {
int len = dfs(v, tree, s);
if (s[u] != s[v]) {
if (len > max1) {
max2 = max1;
max1 = len;
} else if (len > max2) {
max2 = len;
}
}
}
ans = max(ans, max1 + max2 + 1 );
return max1 + 1 ;
}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
func longestPath (parent []int , s string ) int {
n := len(parent )
tree := make([][]int , n )
for i := 1 ; i < n ; i ++ {
tree [parent [i ]] = append(tree [parent [i ]], i )
}
ans := 1
var dfs func (u int ) int
dfs = func (u int ) int {
max1 , max2 := 0 , 0
for _ , v := range tree [u ] {
l := dfs (v )
if s [u ] != s [v ] {
if l > max1 {
max2 = max1
max1 = l
} else if l > max2 {
max2 = l
}
}
}
if max1 + max2 + 1 > ans {
ans = max1 + max2 + 1
}
return max1 + 1
}
dfs (0 )
return ans
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution :
def longestPath (self, parent: list[int], s: str) -> int:
n = len(parent)
tree = [[] for _ in range(n)]
for i in range(1 , n):
tree[parent[i]]. append(i)
self. ans = 1
def dfs (u: int) -> int:
max1 = max2 = 0
for v in tree[u]:
l = dfs(v)
if s[u] != s[v]:
if l > max1:
max2 = max1
max1 = l
elif l > max2:
max2 = l
self. ans = max(self. ans, max1 + max2 + 1 )
return max1 + 1
dfs(0 )
return self. ans
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
impl Solution {
pub fn longest_path (parent: Vec< i32 > , s: String) -> i32 {
let n = parent.len();
let mut tree = vec! [vec! []; n];
for i in 1 .. n {
tree[parent[i] as usize ].push(i);
}
let s_bytes = s.as_bytes();
let mut ans = 1 ;
fn dfs (u: usize , tree: & Vec< Vec< usize >> , s: & [u8 ], ans: & mut i32 ) -> i32 {
let (mut max1, mut max2) = (0 , 0 );
for & v in & tree[u] {
let l = dfs(v, tree, s, ans);
if s[u] != s[v] {
if l > max1 {
max2 = max1;
max1 = l;
} else if l > max2 {
max2 = l;
}
}
}
* ans = (* ans).max(max1 + max2 + 1 );
max1 + 1
}
dfs(0 , & tree, s_bytes, & mut ans);
ans
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
longestPath (parent : number [], s : string ): number {
const n = parent .length ;
const tree : number [][] = Array.from ({length : n }, () => []);
for (let i = 1 ; i < n ; i ++ ) tree [parent [i ]].push (i );
let ans = 1 ;
function dfs (u : number ): number {
let max1 = 0 , max2 = 0 ;
for (const v of tree [u ]) {
const l = dfs (v );
if (s [u ] !== s [v ]) {
if (l > max1 ) {
max2 = max1 ;
max1 = l ;
} else if (l > max2 ) {
max2 = l ;
}
}
}
ans = Math.max (ans , max1 + max2 + 1 );
return max1 + 1 ;
}
dfs (0 );
return ans ;
}
}
Complexity#
⏰ Time complexity: O(n), where n is the number of nodes, since each node is visited once.
🧺 Space complexity: O(n), for the tree and recursion stack.
Method 2 – DFS with Memoization#
Intuition#
We can use memoization to cache the longest path for each node to avoid redundant calculations, especially if the tree is large.
Approach#
Build the tree as an adjacency list.
Use a memoization array to store the longest path for each node.
For each node, recursively compute the longest child paths with different characters.
Update the answer as before.
Code#
Java
Cpp
Go
Python
Rust
Typescript
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution {
int ans = 1;
public int longestPath (int [] parent, String s) {
int n = parent.length ;
List< Integer>[] tree = new List[ n] ;
for (int i = 0; i < n; i++ ) tree[ i] = new ArrayList<> ();
for (int i = 1; i < n; i++ ) tree[ parent[ i]] .add (i);
int [] memo = new int [ n] ;
Arrays.fill (memo, - 1);
dfs(0, tree, s, memo);
return ans;
}
private int dfs (int u, List< Integer>[] tree, String s, int [] memo) {
if (memo[ u] != - 1) return memo[ u] ;
int max1 = 0, max2 = 0;
for (int v : tree[ u] ) {
int len = dfs(v, tree, s, memo);
if (s.charAt (u) != s.charAt (v)) {
if (len > max1) {
max2 = max1;
max1 = len;
} else if (len > max2) {
max2 = len;
}
}
}
ans = Math.max (ans, max1 + max2 + 1);
memo[ u] = max1 + 1;
return memo[ u] ;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
public :
int ans = 1 ;
int longestPath (vector< int >& parent, string s) {
int n = parent.size();
vector< vector< int >> tree(n);
for (int i = 1 ; i < n; ++ i) tree[parent[i]].push_back(i);
vector< int > memo(n, - 1 );
dfs(0 , tree, s, memo);
return ans;
}
int dfs (int u, vector< vector< int >>& tree, string& s, vector< int >& memo) {
if (memo[u] != - 1 ) return memo[u];
int max1 = 0 , max2 = 0 ;
for (int v : tree[u]) {
int len = dfs(v, tree, s, memo);
if (s[u] != s[v]) {
if (len > max1) {
max2 = max1;
max1 = len;
} else if (len > max2) {
max2 = len;
}
}
}
ans = max(ans, max1 + max2 + 1 );
memo[u] = max1 + 1 ;
return memo[u];
}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
func longestPath (parent []int , s string ) int {
n := len(parent )
tree := make([][]int , n )
for i := 1 ; i < n ; i ++ {
tree [parent [i ]] = append(tree [parent [i ]], i )
}
ans := 1
memo := make([]int , n )
for i := range memo {
memo [i ] = - 1
}
var dfs func (u int ) int
dfs = func (u int ) int {
if memo [u ] != - 1 {
return memo [u ]
}
max1 , max2 := 0 , 0
for _ , v := range tree [u ] {
l := dfs (v )
if s [u ] != s [v ] {
if l > max1 {
max2 = max1
max1 = l
} else if l > max2 {
max2 = l
}
}
}
if max1 + max2 + 1 > ans {
ans = max1 + max2 + 1
}
memo [u ] = max1 + 1
return memo [u ]
}
dfs (0 )
return ans
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution :
def longestPath (self, parent: list[int], s: str) -> int:
n = len(parent)
tree = [[] for _ in range(n)]
for i in range(1 , n):
tree[parent[i]]. append(i)
memo = [- 1 ] * n
def dfs (u: int) -> int:
if memo[u] != - 1 :
return memo[u]
max1 = max2 = 0
for v in tree[u]:
l = dfs(v)
if s[u] != s[v]:
if l > max1:
max2 = max1
max1 = l
elif l > max2:
max2 = l
nonlocal ans
ans = max(ans, max1 + max2 + 1 )
memo[u] = max1 + 1
return memo[u]
ans = 1
dfs(0 )
return ans
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
impl Solution {
pub fn longest_path (parent: Vec< i32 > , s: String) -> i32 {
let n = parent.len();
let mut tree = vec! [vec! []; n];
for i in 1 .. n {
tree[parent[i] as usize ].push(i);
}
let s_bytes = s.as_bytes();
let mut ans = 1 ;
let mut memo = vec! [- 1 ; n];
fn dfs (u: usize , tree: & Vec< Vec< usize >> , s: & [u8 ], ans: & mut i32 , memo: & mut Vec< i32 > ) -> i32 {
if memo[u] != - 1 {
return memo[u];
}
let (mut max1, mut max2) = (0 , 0 );
for & v in & tree[u] {
let l = dfs(v, tree, s, ans, memo);
if s[u] != s[v] {
if l > max1 {
max2 = max1;
max1 = l;
} else if l > max2 {
max2 = l;
}
}
}
* ans = (* ans).max(max1 + max2 + 1 );
memo[u] = max1 + 1 ;
memo[u]
}
dfs(0 , & tree, s_bytes, & mut ans, & mut memo);
ans
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
longestPath (parent : number [], s : string ): number {
const n = parent .length ;
const tree : number [][] = Array.from ({length : n }, () => []);
for (let i = 1 ; i < n ; i ++ ) tree [parent [i ]].push (i );
let ans = 1 ;
const memo = new Array(n ).fill (- 1 );
function dfs (u : number ): number {
if (memo [u ] !== - 1 ) return memo [u ];
let max1 = 0 , max2 = 0 ;
for (const v of tree [u ]) {
const l = dfs (v );
if (s [u ] !== s [v ]) {
if (l > max1 ) {
max2 = max1 ;
max1 = l ;
} else if (l > max2 ) {
max2 = l ;
}
}
}
ans = Math.max (ans , max1 + max2 + 1 );
memo [u ] = max1 + 1 ;
return memo [u ];
}
dfs (0 );
return ans ;
}
}
Complexity#
⏰ Time complexity: O(n), since each node’s result is cached and computed once.
🧺 Space complexity: O(n), for the tree, memoization array, and recursion stack.