2246. Longest Path With Different Adjacent Characters

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

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.

Approach overview

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.

Approach 1: DFS with Recursion

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.

Python

from collections import defaultdict

class Solution:
    def longestPath(self, parent: List[int], s: str) -> int:
        n = len(parent)
        children = defaultdict(list)

        for i in range(1, n):
            children[parent[i]].append(i)

        self.max_length = 0

        def dfs(node):
            first_longest, second_longest = 0, 0
            for child in children[node]:
                path_length = dfs(child)
                if s[node] != s[child]:
                    if path_length > first_longest:
                        second_longest = first_longest
                        first_longest = path_length
                    elif path_length > second_longest:
                        second_longest = path_length
            self.max_length = max(self.max_length, first_longest + second_longest + 1)
            return first_longest + 1

        dfs(0)
        return self.max_length

Java

import java.util.*;

class Solution {
    public int longestPath(int[] parent, String s) {
        int n = parent.length;
        List<Integer>[] children = new ArrayList[n];
        for (int i = 0; i < n; i++) {
            children[i] = new ArrayList<>();
        }
        for (int i = 1; i < n; i++) {
            children[parent[i]].add(i);
        }
        int[] max_length = new int[1];
        dfs(0, s, children, max_length);
        return max_length[0];
    }
    
    private int dfs(int node, String s, List<Integer>[] children, int[] max_length) {
        int firstLongest = 0, secondLongest = 0;
        for (int child : children[node]) {
            int pathLength = dfs(child, s, children, max_length);
            if (s.charAt(node) != s.charAt(child)) {
                if (pathLength > firstLongest) {
                    secondLongest = firstLongest;
                    firstLongest = pathLength;
                } else if (pathLength > secondLongest) {
                    secondLongest = pathLength;
                }
            }
        }
        max_length[0] = Math.max(max_length[0], firstLongest + secondLongest + 1);
        return firstLongest + 1;
    }
}

C++

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

class Solution {
public:
    int dfs(int node, const string &s, vector<vector<int>> &children, int &max_length) {
        int first_longest = 0, second_longest = 0;
        for (int child : children[node]) {
            int current_length = dfs(child, s, children, max_length);
            if (s[node] != s[child]) {
                if (current_length > first_longest) {
                    second_longest = first_longest;
                    first_longest = current_length;
                } else if (current_length > second_longest) {
                    second_longest = current_length;
                }
            }
        }
        max_length = max(max_length, first_longest + second_longest + 1);
        return first_longest + 1;
    }

    int longestPath(vector<int>& parent, string s) {
        int n = parent.size();
        vector<vector<int>> children(n);
        for (int i = 1; i < n; ++i) {
            children[parent[i]].push_back(i);
        }
        int max_length = 0;
        dfs(0, s, children, max_length);
        return max_length;
    }
};

JavaScript

var longestPath = function(parent, s) {
    const n = parent.length;
    const children = Array.from({ length: n }, () => []);
    for (let i = 1; i < n; i++) {
        children[parent[i]].push(i);
    }

    let maxLength = 0;

    const dfs = (node) => {
        let firstLongest = 0, secondLongest = 0;
        for (const child of children[node]) {
            const childLength = dfs(child);
            if (s[node] !== s[child]) {
                if (childLength > firstLongest) {
                    secondLongest = firstLongest;
                    firstLongest = childLength;
                } else if (childLength > secondLongest) {
                    secondLongest = childLength;
                }
            }
        }
        maxLength = Math.max(maxLength, firstLongest + secondLongest + 1);
        return firstLongest + 1;
    };

    dfs(0);
    return maxLength;
};

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int dfs(int node, char *s, int **children, int *children_count, int *max_length) {
    int first_longest = 0, second_longest = 0;
    for (int i = 0; i < children_count[node]; i++) {
        int child = children[node][i];
        int path_length = dfs(child, s, children, children_count, max_length);
        if (s[node] != s[child]) {
            if (path_length > first_longest) {
                 second_longest = first_longest;
                 first_longest = path_length;
            } 
            else if (path_length > second_longest) {
                second_longest = path_length;
            }
        }
    }
    *max_length = fmax(*max_length, first_longest + second_longest + 1);
    return first_longest + 1;
}

int longestPath(int* parent, int parentSize, char * s) {
    int n = parentSize;
    int **children = (int **)malloc(n * sizeof(int *));
    int *children_count = (int *)calloc(n, sizeof(int));
    int max_length = 0;

    for (int i = 0; i < n; i++) {
        children[i] = (int *)malloc(n * sizeof(int));
    }

    for (int i = 1; i < n; i++) {
        children[parent[i]][children_count[parent[i]]++] = i;
    }

    dfs(0, s, children, children_count, &max_length);

    for (int i = 0; i < n; i++) {
        free(children[i]);
    }
    free(children);
    free(children_count);

    return max_length;
}

using System;
using System.Collections.Generic;

public class Solution {
    public int LongestPath(int[] parent, string s) {
        int n = parent.Length;
        List<int>[] children = new List<int>[n];
        for (int i = 0; i < n; i++) {
            children[i] = new List<int>();
        }
        for (int i = 1; i < n; i++) {
            children[parent[i]].Add(i);
        }
        int max_length = 0;
        Dfs(0, s, children, ref max_length);
        return max_length;
    }

    private int Dfs(int node, string s, List<int>[] children, ref int max_length) {
        int firstLongest = 0, secondLongest = 0;
        foreach (int child in children[node]) {
            int pathLength = Dfs(child, s, children, ref max_length);
            if (s[node] != s[child]) {
                if (pathLength > firstLongest) {
                    secondLongest = firstLongest;
                    firstLongest = pathLength;
                } else if (pathLength > secondLongest) {
                    secondLongest = pathLength;
                }
            }
        }
        max_length = Math.Max(max_length, firstLongest + secondLongest + 1);
        return firstLongest + 1;
    }
}

This Python solution utilizes a DFS method where a dictionary stores children associated with each node. The maximum path is identified during the recursive search of each node's children, focusing on paths with unique characters.

Complexity

Time Complexity: O(n).
Space Complexity: O(n) due to dictionary storage and potential recursion stack depth.

Try this approach in the editor

Approach 2: Iterative BFS Approach

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.

Python

from collections import deque, defaultdict

class Solution:
    def longestPath(self, parent: List[int], s: str) -> int:
        n = len(parent)
        children = defaultdict(list)
        for i in range(1, n):
            children[parent[i]].append(i)
        queue = deque([(0, 1)]) # stores tuple (node, length of the path)

        maxLength = 1

        while queue:
            node, length = queue.popleft()
            for child in children[node]:
                if s[child] != s[node]:
                    queue.append((child, length + 1))
                    maxLength = max(maxLength, length + 1)

        return maxLength

Java

import java.util.*;

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

        Queue<int[]> queue = new LinkedList<>(); // {node, path length}
        queue.offer(new int[]{0, 1});
        int maxLength = 1;

        while (!queue.isEmpty()) {
            int[] item = queue.poll();
            int node = item[0];
            int length = item[1];

            for (int child : children[node]) {
                if (s.charAt(node) != s.charAt(child)) {
                    queue.offer(new int[]{child, length + 1});
                    maxLength = Math.max(maxLength, length + 1);
                }
            }
        }

        return maxLength;
    }
}

C++

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

class Solution {
public:
    int longestPath(vector<int>& parent, string s) {
        int n = parent.size();
        vector<vector<int>> children(n);
        for (int i = 1; i < n; ++i) {
            children[parent[i]].push_back(i);
        }
        queue<pair<int, int>> q; // (node, current path length)
        q.push({0, 1});
        int max_path = 1;

        while (!q.empty()) {
            auto [node, length] = q.front(); q.pop();
            for (int child : children[node]) {
                if (s[node] != s[child]) {
                    q.push({child, length + 1});
                    max_path = max(max_path, length + 1);
                }
            }
        }
        return max_path;
    }
};

JavaScript

var longestPath = function(parent, s) {
    const n = parent.length;
    const children = Array.from({ length: n }, () => []);
    for (let i = 1; i < n; i++) {
        children[parent[i]].push(i);
    }

    const queue = [[0, 1]]; // [node, length]
    let maxLength = 1;

    while (queue.length > 0) {
        const [node, pathLen] = queue.shift();

        for (const child of children[node]) {
            if (s[node] !== s[child]) {
                queue.push([child, pathLen + 1]);
                maxLength = Math.max(maxLength, pathLen + 1);
            }
        }
    }

    return maxLength;
};

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX_NODES 100000

typedef struct {
    int node;
    int length;
} QueueItem;

static int bfs(int parent[], int n, char s[]) {
    int maxLen = 1;
    QueueItem queue[MAX_NODES];
    int front = 0, rear = 0;
    queue[rear++] = (QueueItem){0, 1};  // Starting from root

    while (front < rear) {
        QueueItem item = queue[front++];
        int node = item.node;
        int length = item.length;

        for (int i = 0; i < n; i++) {
            if (parent[i] == node && s[node] != s[i]) {
                queue[rear++] = (QueueItem){i, length + 1};
                if (length + 1 > maxLen) {
                    maxLen = length + 1;
                }
            }
        }
    }
    return maxLen;
}

int longestPath(int* parent, int parentSize, char* s) {
    return bfs(parent, parentSize, s);
}

using System;
using System.Collections.Generic;

public class Solution {
    public int LongestPath(int[] parent, string s) {
        int n = parent.Length;
        List<int>[] children = new List<int>[n];
        for (int i = 0; i < n; i++) {
            children[i] = new List<int>();
        }
        for (int i = 1; i < n; i++) {
            children[parent[i]].Add(i);
        }

        Queue<(int node, int length)> queue = new Queue<(int, int)>();
        queue.Enqueue((0, 1));
        int maxLength = 1;

        while (queue.Count > 0) {
            var (node, length) = queue.Dequeue();
            foreach (int child in children[node]) {
                if (s[node] != s[child]) {
                    queue.Enqueue((child, length + 1));
                    maxLength = Math.Max(maxLength, length + 1);
                }
            }
        }

        return maxLength;
    }
}

Utilizing a deque for BFS traversal, this Python solution avoids potential recursive depth issues. Paths are explored iteratively, updating the maximum path length encountered for nodes with alternating characters.

Complexity

Time Complexity: O(n).
Space Complexity: O(n) driven by the deque and storage of child relations.

Try this approach in the editor

Approach 3: Tree-shaped DP

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.

TypeScript

function longestPath(parent: number[], s: string): number {
    const n = parent.length;
    const g: number[][] = Array.from({ length: n }, () => []);
    for (let i = 1; i < n; ++i) {
        g[parent[i]].push(i);
    }
    let ans = 0;
    const dfs = (i: number): number => {
        let mx = 0;
        for (const j of g[i]) {
            const x = dfs(j) + 1;
            if (s[i] !== s[j]) {
                ans = Math.max(ans, mx + x);
                mx = Math.max(mx, x);
            }
        }
        return mx;
    };
    dfs(0);
    return ans + 1;
}

func longestPath(parent []int, s string) int {
	n := len(parent)
	g := make([][]int, n)
	for i := 1; i < n; i++ {
		g[parent[i]] = append(g[parent[i]], i)
	}
	ans := 0
	var dfs func(int) int
	dfs = func(i int) int {
		mx := 0
		for _, j := range g[i] {
			x := dfs(j) + 1
			if s[i] != s[j] {
				ans = max(ans, x+mx)
				mx = max(mx, x)
			}
		}
		return mx
	}
	dfs(0)
	return ans + 1
}

Try this approach in the editor

Complexity comparison

Approach	Complexity
DFS with Recursion	Time Complexity: O(n). Space Complexity: O(n) due to dictionary storage and potential recursion stack depth.
Iterative BFS Approach	Time Complexity: O(n). Space Complexity: O(n) driven by the deque and storage of child relations.
Tree-shaped DP	–

Complexity analysis

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.

Frequently asked questions

Is Longest Path With Different Adjacent Characters easy or hard?

The problem is classified as Hard on LeetCode because it requires recognizing a tree dynamic programming pattern. The challenge is correctly tracking the top two valid child paths and updating the global maximum without counting invalid character pairs.

Longest Path With Different Adjacent Characters Python/Java solution

Both Python and Java implementations follow the same DFS tree DP idea. Build the adjacency list, recursively compute the longest valid chain from children, and track the two best paths for each node. Python typically uses recursion with lists, while Java often uses ArrayList for the adjacency structure.

How to solve Longest Path With Different Adjacent Characters in O(n)?

Build an adjacency list from the parent array and run DFS from the root. For every node, compute the longest valid path from its children where the child character differs from the current node. Track the two longest such paths and combine them to update the global answer. Return the best single branch length upward to the parent.

What is the best approach for Longest Path With Different Adjacent Characters?

The most efficient approach is a DFS-based tree dynamic programming solution. During traversal, each node keeps track of the two longest valid child paths whose characters differ from the current node. Combining those paths through the node updates the global maximum path length. This runs in O(n) time because each node and edge is processed once.

Is Longest Path With Different Adjacent Characters asked at Google/Amazon/Meta?

Tree dynamic programming and longest path variations frequently appear in interviews at companies like Google, Amazon, and Meta. Problems similar to this test DFS traversal, tree DP reasoning, and the ability to combine results from child subtrees efficiently.

What data structure is used in Longest Path With Different Adjacent Characters?

The problem primarily uses an adjacency list to represent the tree structure. DFS recursion or a queue for BFS traversal processes nodes, while arrays track the best path lengths from children. This combination of tree representation and graph traversal enables an O(n) solution.

What is the time complexity of Longest Path With Different Adjacent Characters?

The optimal solution runs in O(n) time where n is the number of nodes in the tree. Each node is visited exactly once during traversal, and every edge is evaluated a constant number of times. Space complexity is O(n) due to adjacency lists and recursion stack or auxiliary arrays.

Longest Path With Different Adjacent Characters solution and explanation

The problem

Approach overview

Approach 1: DFS with Recursion

Approach 2: Iterative BFS Approach

Approach 3: Tree-shaped DP

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Longest Path With Different Adjacent Characters solution and explanation

The problem

Approach overview

Approach 1: DFS with Recursion

Approach 2: Iterative BFS Approach

Approach 3: Tree-shaped DP

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems