{x}
blog image

Longest Path With Different Adjacent Characters

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

Solution Explanation: Longest Path With Different Adjacent Characters

This problem asks us to find the longest path in a tree where no two adjacent nodes have the same character. We can solve this efficiently using Depth-First Search (DFS) with a dynamic programming approach.

Approach:

  1. Tree Representation: The input parent array represents a tree structure. We first convert this into an adjacency list representation for easier traversal. The adjacency list g stores for each node, a list of its children.

  2. Depth-First Search (DFS): We perform a DFS traversal starting from the root node (node 0). For each node i, we recursively explore its children.

  3. Dynamic Programming: For each child j of node i, we check if the characters at nodes i and j are different (s[i] != s[j]). If they are different, it means we can extend the path.

    • dfs(j) recursively computes the length of the longest path starting from child j that satisfies the condition.
    • We add 1 to dfs(j) to account for the edge between i and j. This gives us the length x of a path starting at node i and going through j.
    • We maintain two variables:
      • mx: tracks the maximum length of a path extending from the current node i through any of its children.
      • ans: tracks the maximum length of any path found so far in the entire tree.

  4. Updating the Result: When we find a path from i through j with different adjacent characters, we update ans using the formula ans = max(ans, mx + x). This captures the case where we might have two long paths extending from different children of the current node.

  5. Return Value: The function dfs returns mx, the maximum length of a path from the current node. The main function then returns ans + 1 because ans represents the length of the longest path excluding the root node; we add 1 to include the root.

Time and Space Complexity:

  • Time Complexity: O(N) - The DFS algorithm visits each node and edge exactly once. The work done at each node is constant.
  • Space Complexity: O(N) - This is dominated by the adjacency list g and the recursion stack during the DFS. In the worst case (a skewed tree), the recursion depth could be O(N).

Code (Python):

from collections import defaultdict
 
class Solution:
    def longestPath(self, parent: List[int], s: str) -> int:
        g = defaultdict(list)
        for i in range(1, len(parent)):
            g[parent[i]].append(i)
 
        ans = 0
 
        def dfs(i: int) -> int:
            nonlocal ans
            mx = 0
            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
 
        dfs(0)
        return ans + 1

The code in other languages (Java, C++, Go, TypeScript) follows the same logic, differing only in syntax and data structure implementations. They all maintain the same O(N) time and space complexity.