#2246

Hard

auto_awesomeGraph indegree plus topological ordering

LeetCode Problem Workspace

Longest Path With Different Adjacent Characters

Find the longest path in a tree where adjacent nodes have different characters using graph DFS and topological reasoning.

array string tree depth first search graph

Problem Statement

You are given a tree rooted at node 0 represented by an array parent of size n, where parent[i] is the parent of node i and parent[0] == -1. Each node i has a character s[i] assigned from a lowercase English string s.

Return the length of the longest path in this tree such that no two adjacent nodes along the path have the same character. For example, traversing from parent to child nodes while avoiding repeated characters maximizes the path length.

Examples

Example 1

Input: parent = [-1,0,0,1,1,2], s = "abacbe"

Output: 3

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

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 = 1
parent[0] == -1
parent represents a valid tree.
s consists of only lowercase English letters.

Solution Approach

DFS From Root

Perform a depth-first search starting at node 0, recursively computing the longest path in each subtree. At each node, track the two longest child paths that satisfy the adjacent-character constraint to combine into a potential longer path through this node.

Combine Branches Carefully

At every node, consider only child paths whose end character differs from the current node. Maintain the top two lengths to calculate the longest path passing through the current node. Update a global maximum whenever a longer valid path is found.

Leverage Tree Structure Efficiently

Construct the adjacency list from the parent array to traverse children efficiently. Avoid revisiting nodes by leveraging the tree's inherent acyclic structure, which guarantees each node has a single path back to the root, ensuring O(n) time complexity.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(n) because each node is visited once during DFS. Space complexity is O(n) for the adjacency list and recursion stack. The approach scales linearly with tree size, avoiding redundant traversal of nodes or subtrees.

What Interviewers Usually Probe

Focus on graph indegree plus topological ordering.
Watch for combining two longest child paths at each node.
Verify edge cases where characters repeat consecutively along branches.

Common Pitfalls or Variants

Common pitfalls

Counting paths with repeated adjacent characters.
Ignoring second-longest child when combining paths through a node.
Mismanaging recursion stack leading to excessive memory use.

Follow-up variants

Find the longest path where adjacent nodes differ by at least k characters in a string.
Compute the longest path in a k-ary tree with unique node labels.
Determine the maximum path length avoiding a specified subset of characters.

FAQ

What is the main strategy for Longest Path With Different Adjacent Characters?

Use DFS from the root to track longest paths per subtree, combining branches while ensuring adjacent characters differ.

Why is topological reasoning important in this problem?

It ensures nodes are processed from leaves to root correctly, capturing the longest path contributions from all children.

How do I handle adjacent nodes with the same character?

Exclude paths where the child character matches the current node when calculating maximum path lengths.

What is the time complexity for this tree path problem?

O(n) because each node is visited once in DFS and adjacency list construction is linear.

Can GhostInterview help me debug path calculations for example inputs?

Yes, it walks through sample trees step by step, verifying branch combinations and maximum path updates efficiently.

terminal

Solution

Solution 1: 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$.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

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

Continue Practicing

#2328 number of increasing paths in a grid #2368 reachable nodes with restrictions #2115 find all possible recipes from given supplies