2246. Longest Path With Different Adjacent Characters

HardTreeDepth-First SearchGraphTopological SortArrayString

Problem Description

In this LeetCode problem, we are given a special type of graph called a tree. This tree has n nodes, each numbered from 0 to n - 1, and node 0 serves as the root node. The relationships between nodes and their parents are represented by an array parent where parent[i] indicates the parent node of node i. By definition, since node 0 is the root, it has no parent, which is denoted by parent[0] == -1.

Along with the tree structure, each node i is assigned a character given by the string s[i]. The goal is to identify the longest path in the tree where adjacent nodes on the path have different characters. The length of the path is defined as the number of nodes in that path.

The problem is ultimately asking to find the maximum length path in the tree that meets the criteria of having no two consecutive nodes with the same character assigned to them.

Flowchart Walkthrough

To analyze Leetcode problem 2246, "Longest Path With Different Adjacent Characters", let's follow the Flowchart step by step to determine the appropriate algorithm:

Is it a graph?

Yes: In this problem, each node can be represented as a character position in the tree, and edges exist between nodes (characters) that are directly connected in the tree structure.

Is it a tree?

Yes: The structure described involves nodes connected in a hierarchical parent-child relationship without cycles, which fits the definition of a tree.

Since the problem involves a tree structure with a focus on finding the longest path where adjacent characters are different, the algorithm indicated by the flowchart is DFS. This approach is suitable because we need to explore as deep as possible into the tree to check all potential paths and backtrack when necessary.

Conclusion: The flowchart indicates utilizing Depth-First Search (DFS) for this tree-based problem to efficiently find the longest path with different adjacent characters.

Intuition

To solve the problem, one can take a recursive approach, which is commonly used to traverse trees. The intuition here is to use Depth-First Search (DFS) to explore the tree from the root node, tracking the longest path that meets the condition along the way.

The recursive DFS function explores each child of the current node and determines the maximum path length within the subtrees of those children. While traversing, it keeps track of the length of the longest path ending at the current node (mx) and updates the global answer (ans) if a longer path is found.

The critical insight is that, if the current node and its child have different characters, the path can be extended by one. We compare the length of the longest path through each child node and pick the two longest paths to possibly update our answer. The trick is to add the path lengths of two longest non-similar child paths to the global answer. After completing the DFS traversal, the final answer is adjusted by adding one to account for the length of a single node path.

The algorithm essentially constructs a graph from the parent array to track the children of each node and performs DFS starting from the root. During DFS, it checks the characters assigned to the nodes and determines the longest path where adjacent nodes have different characters.

Learn more about Tree, Depth-First Search, Graph and Topological Sort patterns.

Solution Approach

The solution approach involves depth-first search (DFS), a common technique for exploring all the nodes in a tree from a given starting point. The implementation uses a helper function dfs(i) that is designed to recursively travel through the tree starting from node i.

Here's a step-by-step explanation of how the code achieves this:

A dictionary type defaultdict(list) called g is created to store the graph representation of the tree, with each key corresponding to a parent node and its value being the list of child nodes.
The graph g is populated by iterating over the indices of the parent list, starting from index 1 (since index 0 is the root and has no parent), and appending each index i to the list g[parent[i]]. This effectively builds the adjacency list for each node.
A dfs(i) function is defined to use recursive DFS traversal through the tree starting from node i. The function returns the maximum length of the path ending at node i that meets the non-adjacent-character condition.
Within dfs(i), we loop through each child j of the current node i by accessing g[i], and recursively call dfs(j) to continue the exploration further down the tree. The returned value from the recursive call represents the length of the maximum path from child j to a leaf that satisfies the condition, plus one (accounting for the edge to node i).
The function checks if the characters at the current node and its child node are different using s[i] != s[j]. If so, the ans variable (which is tracking the global maximum length) is updated with the sum of mx (the current maximum path length ending at node i) and x (the path length from the child node j), since this forms a valid path with distinct adjacent characters.
The path length x is compared with mx and updates mx if it's longer, ensuring mx always contains the length of the longest path that can be extended from the current node i.

After defining the dfs(i) function and initializing the adjacency list, the DFS traversal is kicked off at the root, dfs(0). Since dfs only counts the length of the path without including the starting node, ans + 1 is returned to account for the root node itself, giving the final answer.

Key Points:

Recursion: The DFS algorithm is implemented using recursion, a natural fit for exploring trees.
Graph Representation: Even though the tree is initially represented as a parent array, it's converted into a graph using adjacency lists for easier traversal.
Non-local Variable: The nonlocal keyword is used for variable ans to allow its modification within the nested dfs function.
Max Tracking: Two local maximum path lengths (mx and x) are used to keep track of the paths and to update the global maximum length ans.

Using DFS and careful updates to the maximum path lengths allow for an efficient search through the tree, yielding the longest path with the required property.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's take a small example to illustrate the solution approach:

Suppose we have a tree with n = 5 nodes and the following parent relationship array: parent = [-1, 0, 0, 1, 1]. This means that node 0 is the root, node 1 and node 2 are children of node 0, and nodes 3 and 4 are children of node 1. The characters assigned to each node are represented by the string s = "ababa".

Now we will walk through the steps of the DFS solution to find the longest path with different adjacent characters:

First, we'll create the graph g from the parent array, which will look like this:

g = {
  0: [1, 2],
  1: [3, 4]
}

We define the dfs(i) function to start the DFS traversal. We will also initialize ans = 0 to store the length of the longest path.
We start the DFS from the root node dfs(0):
- Since node 0 has two children (1 and 2), we call dfs(1) and dfs(2).
In the dfs(1) call:
- Node 1 has children 3 and 4. We call dfs(3) and dfs(4) respectively.
- The character at node 1 is b, and at node 3 it's a. Since they are different, ans can be updated to 2 if dfs(3) returns 1.
- Similarly, dfs(4) returns 1 because node 4's character is similar to 1, making the path length 1. Now ans would be updated to 3 because mx + x = 2 + 1 (path through node 1 to node 3 and then from node 1 to node 4).
For dfs(2), since node 2 has no child and its character is a which is different from the root's character a, dfs(2) will simply return 1.
As we return back to dfs(0), we check the character at node 0, which is a, and compare it with its children's characters. Node 2 has the same character, so we cannot form a longer path through node 2. The longest path at this point is from node 0 to node 1 to node 3, and node 1 to node 4.
After traversing all nodes, ans + 1 will give us the final answer. We add one because ans is tracking the number of edges in the longest path, and we want to count the number of nodes, which is one more than the number of edges.

In this particular example, the longest path with different adjacent characters has a length of 4: through the nodes 0 -> 1 -> 3 and 1 -> 4. Our ans was updated to 3 at most during the DFS traversal, and thus the final answer will be ans + 1 = 4.

Key Points of Clarification:

While calculating the path lengths, we consider the length as the number of edges between nodes on the path.
We need to return ans + 1 at the end of the traversal since the counting starts at 0 and the problem asks for the number of nodes in the path, not the number of edges.
This example demonstrates how dfs helps in efficiently finding and updating the longest path in the tree with the desired property.

Solution Implementation

1from collections import defaultdict
2from typing import List
3
4class Solution:
5    def longestPath(self, parents: List[int], s: str) -> int:
6        # Depth-First Search function to explore the graph
7        def dfs(node_index: int) -> int:
8            max_depth = 0  # Stores the maximum depth of child nodes
9            nonlocal longest_path_len  # Refers to the non-local variable 'longest_path_len'
10            for child_index in graph[node_index]:  # Iterate through child nodes
11                child_depth = dfs(child_index) + 1  # Depth of child is parent depth + 1
12                # If the characters are different, we can extend the path
13                if s[node_index] != s[child_index]:
14                    longest_path_len = max(longest_path_len, max_depth + child_depth)
15                    max_depth = max(max_depth, child_depth)
16            return max_depth  # Return the maximum depth encountered
17
18        # Build the graph from the parent list
19        graph = defaultdict(list)
20        # Create adjacency list for each node except the root
21        for index in range(1, len(parents)):
22            graph[parents[index]].append(index)
23
24        longest_path_len = 0  # Initialize the answer to track the maximum length of the path
25        dfs(0)  # Start DFS from the root node
26      
27        # longest_path_len is the length of the path without root.
28        # We add 1 to include the root in the final path length.
29        return longest_path_len + 1
30

1class Solution {
2    private List<Integer>[] graph; // Graph represented as an adjacency list
3    private String labels; // String storing the labels of each node
4    private int maxPathLength; // The maximum length of the path found that conforms to the question's rules
5
6    // Method that returns the longest path where the consecutive nodes have different labels
7    public int longestPath(int[] parents, String labels) {
8        int n = parents.length;
9        graph = new List[n]; // Initialize the graph to the size of the parent array
10        this.labels = labels; // Assign the global variable to the input labels
11        Arrays.setAll(graph, k -> new ArrayList<>()); // Initialize each list in the graph
12
13        // Construct the graph from the parent array
14        for (int i = 1; i < n; i++) {
15            graph[parents[i]].add(i);
16        }
17
18        dfs(0); // Start the depth-first search from the root node (0)
19        return maxPathLength + 1; // Add 1 because the path length is edges count, so nodes count is edges count + 1
20    }
21
22    // Helper method for depth-first search that computes the longest path
23    private int dfs(int node) {
24        int maxDepth = 0; // The max depth of the subtree rooted at the current node
25        // Iterate through the children of the current node
26        for (int child : graph[node]) {
27            int depth = dfs(child) + 1; // Get the depth for each child and increment it as we move down
28            // Only consider paths whose consecutive nodes have different labels
29            if (labels.charAt(node) != labels.charAt(child)) {
30                maxPathLength = Math.max(maxPathLength, maxDepth + depth); // Update maxPathLength if needed
31                maxDepth = Math.max(maxDepth, depth); // Update the maxDepth if the current depth is greater
32            }
33        }
34        return maxDepth; // Return the max depth found for this node's subtree
35    }
36}
37

1#include <vector>
2#include <string>
3#include <functional> // Include for std::function
4
5class Solution {
6public:
7    // Function to find the longest path where each character is different 
8    // from its parent in a tree defined by parent-child relationships and node values given by string s.
9    int longestPath(vector<int>& parent, string& s) {
10        int numNodes = parent.size(); // Total number of nodes in the tree.
11        vector<vector<int>> graph(numNodes);
12      
13        // Build the adjacency list representation of the tree from the parent array.
14        for (int i = 1; i < numNodes; ++i) {
15            graph[parent[i]].push_back(i);
16        }
17      
18        // Variable to store the length of the longest path found.
19        int longestPathLength = 0;
20      
21        // Define the depth-first search (DFS) function using lambda notation.
22        std::function<int(int)> dfs = [&](int currentNode) -> int {
23            // The maximum path length through this node.
24            int maxLengthThroughCurrent = 0;
25          
26            // Explore all child nodes of the current node.
27            for (int child : graph[currentNode]) {
28                // Recursively perform DFS from the child node.
29                int pathLengthFromChild = dfs(child) + 1; // +1 for the edge from the current node to the child node.
30              
31                // If the current node and the child have different characters,
32                // try to extend the path.
33                if (s[currentNode] != s[child]) {
34                    // Update the longest path if combining two paths through this node
35                    // results in a longer path.
36                    longestPathLength = max(longestPathLength, maxLengthThroughCurrent + pathLengthFromChild);
37                  
38                    // Update the maximum length of the path that goes through the current node.
39                    maxLengthThroughCurrent = max(maxLengthThroughCurrent, pathLengthFromChild);
40                }
41            }
42          
43            // Return the max length of the path through the current node to its parent.
44            return maxLengthThroughCurrent;
45        };
46      
47        // Start DFS from the root node (0).
48        dfs(0);
49      
50        // Return the length of the longest path. We add 1 because the path length
51        // is the number of nodes on the path, but longestPathLength stores the number of edges.
52        return longestPathLength + 1;
53    }
54};
55

1function longestPath(parents: number[], s: string): number {
2    // The number of nodes in the tree
3    const nodeCount = parents.length;
4  
5    // Adjacency list representing the tree graph
6    // Each index corresponds to a node, which contains an array of its children
7    const graph: number[][] = Array.from({ length: nodeCount }, () => []);
8  
9    // Building the graph from the parent array
10    for (let i = 1; i < nodeCount; ++i) {
11        graph[parents[i]].push(i);
12    }
13  
14    // The variable to store the length of the longest path
15    let longestPathLength = 0;
16  
17    // Depth-First Search function to explore nodes
18    const dfs = (node: number): number => {
19        // To hold the max path through the current node
20        let maxPathThroughNode = 0;
21
22        // Iterating through each child of the current node
23        for (const child of graph[node]) {
24            // Determine the path length including this child if unique character
25            const childPathLength = dfs(child) + 1;
26
27            // We only consider this path if it contains unique characters
28            if (s[node] !== s[child]) {
29                // Update the longest path combining paths from two children
30                longestPathLength = Math.max(longestPathLength, maxPathThroughNode + childPathLength);
31                // Update the max path length through this node with the length including the current child
32                maxPathThroughNode = Math.max(maxPathThroughNode, childPathLength);
33            }
34        }
35
36        // Return the max path length from current node's children
37        return maxPathThroughNode;
38    };
39
40    // Start Depth-First Search from the root node (0)
41    dfs(0);
42  
43    // The longest path will be longestPathLength + 1, as the count starts from 0
44    return longestPathLength + 1;
45}
46

Time and Space Complexity

Time Complexity

The time complexity of the code is O(N), where N is the number of nodes in the input list parent. This complexity arises because the code visits every node exactly once through depth-first search (DFS). Each node processing (not counting the DFS recursion) takes constant time, leading to a linear time complexity relative to the number of nodes.

Space Complexity

The space complexity of the code is also O(N). This space is required for the adjacency list g and the call stack during the recursive DFS calls. Each node can contribute at most one frame to the call stack (in the case of a linear tree), and the adjacency list can store up to 2(N - 1) edges (considering an undirected representation of the tree for understanding, although the actual directed edges are less and do not contribute to space more than O(N)). As a result, the overall space complexity remains linear with respect to N.

Learn more about how to find time and space complexity quickly using problem constraints.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Question 1 out of 10

Depth first search is equivalent to which of the tree traversal order?

Pre-order traversal

Post-order traversal

In-order traversal

Level-order traversal

I don’t know