2246. Longest Path With Different Adjacent Characters

https://leetcode.com/problems/longest-path-with-different-adjacent-characters/description/

Python

DFS

from collections import defaultdict


class Solution:
    def longestPath(self, parent: List[int], s: str) -> int:
        mapper = defaultdict(set)
        for i, p in enumerate(parent):
            mapper[p].add(i)

        def dfs(node):
            first, second = 0, 0
            for child in mapper[node]:
                child_path = dfs(child)
                if s[child] == s[node]:
                    continue

                if child_path >= first:
                    first, second = child_path, first
                elif child_path > second:
                    second = child_path
            self.ans = max(self.ans, 1+first+second)
            return 1 + first
        self.ans = 0

        dfs(0)
        return self.ans