Longest Path With Different Adjacent Characters LeetCode solution in Python

1
class Solution:
2
    def longestPath(self, parent: list[int], s: str) -> int:
3
        def l_path_and_chain(
4
            tree: dict[int, list[int]], s: str, root: int
5
        ) -> tuple[int, int]:
6
            lp = lc1 = lc2 = 0
7
            for child, path, chain in (
8
                (c, *l_path_and_chain(tree, s, c)) for c in tree[root]
9
            ):
10
                lp = max(lp, path)
11
                if s[child] != s[root]:
12
                    *_, lc2, lc1 = sorted((chain, lc2, lc1))
13

14
            return max(lp, lc1 + lc2 + 1), lc1 + 1
15

16
        t = defaultdict(list)
17
        for c, p in enumerate(parent):
18
            t[p].append(c)
19
        return l_path_and_chain(t, s, 0)[0]