2246. Longest Path With Different Adjacent Characters

[box-lin]

Memo DFS

class Solution:
    def longestPath(self, parent: List[int], s: str) -> int:
        @cache
        def dfs(node, prev):
            maxpath = 1
            for nei in adjmap[node]:
                # loop or adjacent same
                if nei == prev or s[node] == s[nei]:
                    continue
                maxpath = dfs(nei, node) + 1
            return maxpath

        adjmap = defaultdict(set)
        for child, par in enumerate(parent):
            if par == -1: continue
            adjmap[child].add(par)
            adjmap[par].add(child)

        ans = 1
        n = len(parent)
        for node in range(n):
            ans = max(ans, dfs(node, -1))
        return ans

[box-lin]

TLE Version

class Solution:
    def longestPath(self, parent: List[int], s: str) -> int:
        def dfs(node, prev, cnt):
            nonlocal ans
            for nei in adjmap[node]:
                # loop or adjacent same
                if nei == prev or s[node] == s[nei]:
                    continue
                cnt += 1
                dfs(nei, node, cnt)
                ans = max(ans, cnt)

        adjmap = defaultdict(set)
        for child, par in enumerate(parent):
            if par == -1: continue
            adjmap[child].add(par)
            adjmap[par].add(child)

        ans = 1
        n = len(parent)
        for node in range(n):
            dfs(node, -1, 1)
        return ans

[box-lin]

O(n) time, O(n) space

class Solution:
    def longestPath(self, parent: List[int], s: str) -> int:
        n = len(parent)
        g = [[] for _ in range(n)]
        for i in range(1, n):
            g[parent[i]].append(i)

        ans = 0
        def dfs(x: int) -> int:
            nonlocal ans
            max_len = 0
            for y in g[x]:
                len = dfs(y) + 1
                if s[y] != s[x]:
                    ans = max(ans, max_len + len)
                    max_len = max(max_len, len)
            return max_len
        dfs(0)
        return ans + 1