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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Longest Path With Different Adjacent Characters

Number: 2364

Difficulty: Hard

Paid? No

Companies: Uber, Microsoft, Amazon, Hudson River Trading

Problem Description

Given a tree (an acyclic connected graph) rooted at node 0 represented by an array called parent, where parent[i] is the parent of node i (with parent[0] = -1), and a string s where s[i] represents the character assigned to node i, find the length of the longest path in the tree such that adjacent nodes on the path have different characters.

Key Insights

  • The tree structure guarantees a unique path between any two nodes.
  • A depth-first search (DFS) can be used to explore each subtree and aggregate the maximum valid branch lengths.
  • At each node, only child paths with a different character than the current node can be extended.
  • Combining the two longest valid branches stemming from a node gives the candidate longest path that passes through that node.
  • A global variable is maintained to track the overall longest valid path found during traversal.

Space and Time Complexity

Time Complexity: O(n) - Each node is visited once. Space Complexity: O(n) - For recursion stack and storage of the tree structure.

Solution

We solve the problem using a DFS traversal. First, we build an adjacency list (child list) from the parent array to represent the tree. For each node, we perform a DFS that returns the length of the longest valid path starting from that node (including itself) where the adjacent characters differ. For every node, we consider all its children and update the two longest valid branch lengths only if their characters differ from the current node. The candidate longest path passing through a node is the sum of the two longest valid branch lengths plus 1 (for the current node). We update a global maximum with this value at every node. Finally, the DFS returns the overall maximum path length.

Code Solutions

# Python solution for "Longest Path With Different Adjacent Characters"

def longestPath(parent, s):
    from collections import defaultdict
    
    # Build the adjacency list for the tree
    tree = defaultdict(list)
    n = len(parent)
    for node in range(1, n):
        tree[parent[node]].append(node)
    
    # Global variable to store the longest valid path length
    max_path = 0

    # DFS function to compute the longest valid branch starting from the current node
    def dfs(node):
        nonlocal max_path
        # The two longest valid branch lengths from the children (without current node)
        longest, second_longest = 0, 0
        
        # Explore each child
        for child in tree[node]:
            branch_length = dfs(child)  # Compute branch length for child subtree
            # Only extend the branch if the character at child is different
            if s[child] != s[node]:
                if branch_length > longest:
                    second_longest = longest
                    longest = branch_length
                elif branch_length > second_longest:
                    second_longest = branch_length
        
        # Update the global maximum with the sum of the two best branches from the node plus itself
        max_path = max(max_path, longest + second_longest + 1)
        # Return the length of the longest branch including the current node
        return longest + 1

    dfs(0)
    return max_path

# Example usage:
# parent = [-1,0,0,1,1,2]
# s = "abacbe"
# print(longestPath(parent, s))  # Output: 3
← Back to All Questions