LeetCode 2246 - Longest Path With Different Adjacent Characters

Difficulty: 🔴 Hard
Topics: Array, String, Tree, Depth-First Search, Graph Theory, Topological Sort

Solution

Problem Understanding

The problem gives a tree with n nodes labeled 0 to n-1, rooted at node 0. The tree is represented using a parent array, where parent[i] indicates the parent of node i. Node 0 has no parent, so parent[0] == -1. Each node also has a character assigned from string s, where s[i] corresponds to node i.

We are asked to find the longest path in the tree such that no two adjacent nodes on the path share the same character. The path does not have to start at the root; it can be any connected sequence of nodes in the tree. The result is the length of this path in terms of the number of nodes.

The constraints show that n can be as large as 10^5, which rules out brute-force solutions that explore all possible paths naively. The tree is valid, so there are no cycles, and s contains only lowercase letters.

Important edge cases include small trees (like a single node), trees where all characters are the same, and trees that are essentially a chain or star shape.

Approaches

A brute-force approach would be to explore all paths in the tree and check if adjacent characters differ. One could do this with a recursive depth-first search (DFS) from every node and keep track of the maximum path length. While this approach would eventually find the correct answer, it is prohibitively slow, since exploring all paths in a tree with n = 10^5 nodes can take exponential time.

The optimal approach uses DFS in a bottom-up manner. For each node, we compute the length of the longest path starting from this node and going down, considering only children with different characters. While processing a node, we track the two longest child paths with different characters. The maximum path that passes through the current node can then be formed by summing these two longest child paths plus one for the current node itself. By maintaining a global maximum while traversing the tree once, we achieve an efficient solution.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(2^n)	O(n)	Explore all paths from all nodes, too slow for large n
Optimal	O(n)	O(n)	Single DFS with tracking of longest child paths, efficient for large n

Algorithm Walkthrough

Convert the parent array into a tree structure, typically an adjacency list, to easily access children of any node.
Initialize a global variable max_path to track the maximum path length found.
Define a recursive DFS function that takes a node u as input.
For each child v of u, recursively call DFS to get the longest path starting from v.
If s[v] != s[u], consider this path as a candidate to extend the path through u.
Track the two longest valid child paths for node u.
Update the global max_path as the sum of the two longest child paths plus one (including u).
Return the length of the longest valid single child path plus one to the parent call.
After DFS finishes at the root, max_path contains the length of the longest path satisfying the constraints.

Why it works: Each node calculates the best path starting from itself while considering its children. By keeping track of the top two longest child paths, we ensure that any path passing through a node and including multiple branches is accounted for. Since we visit each node exactly once, we guarantee correctness and efficiency.

Python Solution

from typing import List, Dict

class Solution:
    def longestPath(self, parent: List[int], s: str) -> int:
        n = len(parent)
        tree: Dict[int, List[int]] = {i: [] for i in range(n)}
        for i in range(1, n):
            tree[parent[i]].append(i)
        
        self.max_path = 1

        def dfs(node: int) -> int:
            longest = 0
            second_longest = 0
            for child in tree[node]:
                child_path = dfs(child)
                if s[child] != s[node]:
                    if child_path > longest:
                        second_longest = longest
                        longest = child_path
                    elif child_path > second_longest:
                        second_longest = child_path
            self.max_path = max(self.max_path, longest + second_longest + 1)
            return longest + 1

        dfs(0)
        return self.max_path

The implementation first builds an adjacency list for the tree, then performs DFS starting from the root. Each DFS call returns the longest path starting from that node, while the global max_path is updated to reflect the best path found so far. The longest and second_longest variables ensure that paths passing through a node and branching to two children are correctly considered.

Go Solution

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)
    }

    maxPath := 1

    var dfs func(int) int
    dfs = func(node int) int {
        longest, secondLongest := 0, 0
        for _, child := range tree[node] {
            childPath := dfs(child)
            if s[child] != s[node] {
                if childPath > longest {
                    secondLongest = longest
                    longest = childPath
                } else if childPath > secondLongest {
                    secondLongest = childPath
                }
            }
        }
        if longest+secondLongest+1 > maxPath {
            maxPath = longest + secondLongest + 1
        }
        return longest + 1
    }

    dfs(0)
    return maxPath
}

In Go, we use slices to represent the adjacency list. The DFS function is implemented as a closure to allow access to maxPath without global variables. Otherwise, the logic mirrors the Python solution closely.

Worked Examples

Example 1:

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

Tree structure:

0(a)
├─1(b)
│ ├─3(a)
│ └─4(c)
└─2(a)
   └─5(e)

DFS traversal:

Node 3 returns 1 (no children).
Node 4 returns 1.
Node 1 sees children 3 and 4. Longest two paths with different characters: 1 (3), 1 (4). Update max_path = 1+1+1 = 3.
Node 5 returns 1.
Node 2 sees child 5 with different character. Longest = 1. max_path remains 3.
Node 0 sees children 1 and 2. Child 1 max path = 2 (1+1?), child 2 max path = 2. They cannot be combined through 0 because characters differ? Actually 0(a) vs 2(a) same, so only 1 child considered (child 1). Max_path remains 3.

Final result: 3

Example 2:

parent = [-1,0,0,0], s = "aabc"

Tree structure:

0(a)
├─1(a)
├─2(b)
└─3(c)

DFS:

Node 1 returns 1 (same character as 0, cannot extend).
Node 2 returns 1 (different, longest =1).
Node 3 returns 1 (different, second longest=1).
Node 0 combines two longest paths 1+1+1=3. max_path = 3.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Each node is visited once, and we process each child once.
Space	O(n)	Storing adjacency list and call stack for DFS.

We traverse the tree once, ensuring linear time, and we store the adjacency list, which requires space proportional to the number of nodes.

Test Cases

# Provided examples
assert Solution().longestPath([-1,0,0,1,1,2], "abacbe") == 3  # example 1
assert Solution().longestPath([-1,0,0,0], "aabc") == 3        # example 2

# Single node
assert Solution().longestPath([-1], "a") == 1                  # smallest tree

# All characters same
assert Solution().longestPath([-1,0,1,2], "aaaa") == 1         # cannot extend path

# Chain with alternating characters
assert Solution().longestPath([-1,0,1,2,3], "ababab") == 6    # entire chain

# Star tree with distinct children
assert Solution().longestPath([-1,0,0,0,0], "abcde") == 2     # path is root -> child

Test	Why
Provided examples	Validate correctness against problem statement
Single node	Edge case with minimum input size
All characters same	Edge case where longest path