We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Longest Path With Different Adjacent Characters

Difficulty: Hard

Problem Description

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.

Key Insights

  • The problem requires finding the longest path in a tree where adjacent nodes have different characters.
  • A Depth-First Search (DFS) can be utilized to traverse the tree and calculate the longest valid path.
  • Maintaining a record of the longest path lengths from each node helps in calculating the overall longest path efficiently.
  • The tree structure allows for easy traversal given the parent relationships.

Space and Time Complexity

Time Complexity: O(n)
Space Complexity: O(n)

Solution

To solve this problem, we can use a Depth-First Search (DFS) approach. We will traverse the tree starting from the root node. For each node, we will keep track of the longest paths from its children that have different characters than the current node. The algorithm will involve the following steps:

  1. Build the tree as an adjacency list from the parent array.
  2. Perform a DFS from the root node:
    • For each node, check its children and compute the longest paths that can be formed with different characters.
    • Update the overall longest path found during the DFS traversal.
  3. Return the maximum length of the valid path found.

Code Solutions

def longestPath(parent, s):
    from collections import defaultdict

    # Build the adjacency list for the tree
    tree = defaultdict(list)
    for child in range(1, len(parent)):
        tree[parent[child]].append(child)

    max_length = 0

    def dfs(node):
        nonlocal max_length
        longest1, longest2 = 0, 0  # Longest and second longest paths

        for child in tree[node]:
            child_length = dfs(child)
            # Check if the characters are different
            if s[child] != s[node]:
                if child_length > longest1:
                    longest2 = longest1
                    longest1 = child_length
                elif child_length > longest2:
                    longest2 = child_length

        # Update the maximum length found
        max_length = max(max_length, longest1 + longest2 + 1)  # +1 for the current node
        return longest1 + 1  # Return the longest path from this node

    dfs(0)
    return max_length
← Back to All Questions