Longest Path With Different Adjacent Characters

Longest Path With Different Adjacent Characters

What is this problem about?

This graph problem provides a tree (a connected, undirected graph with no cycles) where each node is assigned a specific character. Your task is to find the length of the longest path in this tree such that no two adjacent nodes on the path share the same character. The path does not need to pass through the root.

Why is this asked in interviews?

This problem is an excellent test of a candidate's Tree algorithms and Depth-First Search (DFS) capabilities. It goes beyond simple tree traversals by requiring you to compute paths that can "bend" at a node. Interviewers use it to see if you understand how to merge branch results (left longest path + right longest path) while strictly enforcing node-level constraints.

Algorithmic pattern used

This problem is solved using Depth-First Search (DFS) on Trees. For any given node, the longest valid path that passes through it is formed by combining the top two longest valid paths coming from its children. Your DFS function should return the longest single-directional path starting from the current node and going down. As you compute this for each child, if the child's character differs from the parent's, you update the top two path lengths and keep a running global maximum of top1 + top2 + 1.

Example explanation

Suppose a tree where node 0 is 'a', node 1 is 'b', and node 2 is 'a'. Node 0 is the parent of 1 and 2. DFS starts at 0 ('a').

• Explores child 1 ('b'). Node 1 has no children. Returns length 1.
  • Since 'b' != 'a', we accept this path. Length from 1 is 1.
• Explores child 2 ('a'). Node 2 has no children. Returns length 1.
  • Since 'a' == 'a', we REJECT this path. We cannot step from 0 to 2. Back at node 0, our longest valid child path is from node 1 (length 1). The second longest is 0. The longest path through node 0 is 1 (node 1) + 0 + 1 (node 0 itself) = 2. The path is 1 -> 0.

Common mistakes candidates make

Candidates often try to return the full "bent" path from the DFS function. The recursive function should only return the longest straight path downwards to be used by its parent. The full "bent" path (which forms a V-shape) should be calculated and stored in a global max variable during the visit. Another mistake is forgetting to initialize the global max to 1, as a single node itself is a valid path of length 1.

Interview preparation tip

When tackling the Longest Path With Different Adjacent Characters interview pattern, practice the "Top 2 Children" pattern. Many advanced tree problems (like Binary Tree Maximum Path Sum) require you to find the two largest values from a node's children to form an inverted-V path. Mastering how to maintain a max1 and max2 variable inside a loop over children is critical.