Longest Path With Different Adjacent Characters
01 · Problem
You are given a tree with n nodes labelled 0 to n - 1, rooted at node 0, described by an array parent where parent[i] is the parent of node i. The root has parent[0] == -1.
You are also given a string s of length n, where s[i] is the character written on node i.
Return the number of nodes on the longest path in the tree in which no two adjacent nodes have the same character. A path may start and end at any nodes and does not have to pass through the root. A single node is always a valid path of length 1.
02 · Examples
parent = [-1,0,0,1,1,2], s = "abacbe"
3
The path 3 -> 1 -> 0 has characters c, b, a, all different from their neighbours. Node 2 cannot extend it because 0 and 2 are both 'a'.
parent = [-1,0,0,0], s = "aabc"
3
The path 2 -> 0 -> 3 has characters b, a, c. Node 1 cannot join because it shares 'a' with node 0.
parent = [-1,0,1,2], s = "aaaa"
1
Every pair of adjacent nodes shares the character 'a', so the best path is a single node.
03 · Constraints
- 01n == parent.length == s.length
- 021 <= n <= 105
- 03parent[0] == -1, and 0 <= parent[i] < n for i >= 1
- 04parent describes a valid tree.
- 05s consists of lowercase English letters only.
04 · Optimal complexity
- Time
- O(n)
- Space
- O(n)
Practice it alone or rehearse it as an interview.
Practice Mode gives you an editor and test runs, nothing else. AI Interview Mode puts a voice interviewer on the other side, adds a clock, and ends with a scored summary of the round.