Longest Alternating a/b Path in a Tree
Updated
Problem statement
You are given a tree with n nodes numbered from 0 to n - 1. Node 0 is the root. The array parent describes the tree: parent[0] is -1, and for every other node i, parent[i] is the node directly above i. A parent can have a larger number than its child.
Each node holds one letter, 'a' or 'b'. The letter of node i is labels[i].
A path is a list of different nodes in which each node is joined to the next one by a tree edge. A path does not have to start at the root or end at a leaf. It can go up to some node and then down a different branch. A single node is also a path.
A path is alternating if no two neighboring nodes on it have the same letter. Return the number of nodes on the longest alternating path.
The tree can be a single chain of 10^4 nodes, so a recursive solution must be able to go that deep.
Function
longestAlternatingPath(parent: int[], labels: String) → intExamples
Example 1
parent = [-1,0,0,1,1,3,4]labels = "abbaaba"return = 5Edges 0-1, 0-2, 1-3, 1-4 and 3-5 join nodes with different letters. Edge 4-6 joins two 'a' nodes, so node 6 can never be next to node 4 on an alternating path.
The path 5 → 3 → 1 → 0 → 2 has the letters b, a, b, a, b. No two neighbors match, and it has 5 nodes. It goes up from node 5 to the root and then down to node 2.
No alternating path is longer, so the answer is 5.
Example 2
parent = [-1,0,0]labels = "aaa"return = 1Every node is labeled 'a', so any path with two or more nodes has two neighbors with the same letter. A single node is still a path with no neighbors, so the answer is 1.
Example 3
parent = [-1,3,0,2,1,3]labels = "aaabba"return = 4Here a parent can have a larger number than its child. For example, parent[1] = 3. The edges are 0-2, 2-3, 3-1, 1-4 and 3-5.
Nodes 0 and 2 are both 'a', so the root cannot be next to node 2. Node 0 has no other neighbor, so it is not on any longer path.
The path 4 → 1 → 3 → 2 has the letters b, a, b, a and 4 nodes. The path 4 → 1 → 3 → 5, which turns at node 3, also has 4 nodes. Without the blocked edge, the usable part has the five nodes 1 to 5, and three of them (2, 4 and 5) have only one usable neighbor. A path has only two ends, so it cannot hold all five nodes. The answer is 4.
Constraints
n == parent.length == labels.length1 <= n <= 10^4parent[0] == -10 <= parent[i] <= n - 1for everyifrom1ton - 1- Following
parentlinks from any node always reaches node0, soparentdescribes one tree rooted at node0. labelscontains only the letters'a'and'b'.
More Hudson River Trading Online Assessment questions
- Count Palindrome Addition ChoicesOA · Seen Nov 2026
- Count Multiples of Three with Two SevensOA · Seen Oct 2026
- Recursively Expanded Shell Command CountsOA · Seen Oct 2026
- Rotate Matrix Regions Around the DiagonalsOA · Seen Oct 2026
- Maximum Diamond SumOA · Seen Oct 2026
- Smallest Most-Lit Street PositionOA · Seen Oct 2026
- Rearrange String by Alternating EndsOA · Seen Sep 2026
- Most Items Within Budget from a Start IndexOA · Seen Sep 2026
- Count Sawtooth SubarraysOA · Seen Aug 2026
- Backtick Identifier ConverterOA · Seen Jun 2026
Similar questions at other companies
- Maximum Data Transfer TimeMicrosoft · OAMicrosoft interview questions
- Best Sum Downward Tree PathCitadel · OACitadel interview questions
- Longest Transfer Time in a Server TreeRippling · OARippling interview questions
- Binary Tree Level OrderMorgan Stanley · OAMorgan Stanley interview questions
- Maximum Reservoir PowerWells Fargo · OAWells Fargo interview questions
- Minimum Leaf Path Sum over All RootsInfosys · OAInfosys interview questions
- Part 2: Batch Access ReviewScale AI · OAScale AI interview questions
- Binary Tree CamerasAmazon · OA · PHONE SCREEN
- Maximum Sum Path Between Two Leaf NodesGoogle · OAGoogle interview questions
- Special Diameter EndpointsAgoda · OAAgoda interview questions