Longest Path With Different Adjacent Characters
Real-world version: The Longest Run of Unlike PostsThe statement here is our own: the same inputs, outputs and technique.
A tree has posts numbered 0 through n - 1, and post 0 sits at the top. above[i] names the post directly above post i, and above[0] is -1. Each post carries one lowercase letter, given by marks.
A run is a path through the tree that never repeats a post and along which no two neighbouring posts carry the same letter.
Return the largest number of posts a run can hold.
Examples
Example 1
- Input
- above = [-1, 0, 1, 2, 3], marks = "abcde"
- Output
- 5
The posts form a single chain and no two neighbours share a letter, so the whole chain is one run.
Example 2
- Input
- above = [-1, 0], marks = "aa"
- Output
- 1
Both posts carry the same letter, so no run can hold the two of them.
Example 3
- Input
- above = [-1, 0, 0, 0, 0, 0], marks = "abcdef"
- Output
- 3
Five posts hang off the top one, all carrying different letters, so a run can come up one branch, through the top, and down another.
Constraints
- 1 <= above.length <= 10^5
- above.length == marks.length
- above[0] == -1
- above describes a tree with post 0 at the top
- marks holds only lowercase English letters
The signature
The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.
def longest_path(above: list[int], marks: str) -> int:public int longestPath(int[] above, String marks)Checking your plan…
How this problem was checked
- Passed: Reference solution run against 15 test cases: 15 passed
- Passed: 3 worked examples confirmed by running the code
- Passed: 0 eight-word sequences shared with the parent problem's text
- Passed: Agrees with an independent brute-force solution on random inputs
- Passed: Test set shown to catch deliberately broken solutions
- Passed: Reviewed by a separate quality pass
- Passed: Function arity matches the parent problem's