2246. Longest Path With Different Adjacent Characters - cocoder39/coco39_LC GitHub Wiki

2246. Longest Path With Different Adjacent Characters

a variant of path sum

class Solution:
    def __init__(self):
        self.res = 1

    def longestPath(self, parent: List[int], s: str) -> int:
        n = len(s)
        children = collections.defaultdict(list)
        for i in range(1, n):
            children[parent[i]].append(i)
        self.dfs(0, children, s)
        return self.res
    
    def dfs(self, node, children, s): # return max straight path with node included 
        if node not in children: # leave node
            return 1
        
        first, second = 0, 0
        for child in children[node]:
            candidate = self.dfs(child, children, s) # if we do s[node] == s[child] check first then we would miss results contributed by lower layer 

            if s[node] == s[child]:
                continue
            if candidate > first:
                second = first
                first = candidate
            elif candidate > second:
                second = candidate
        
        # each node contributes 2 paths: straight path eg 0, 1 vs cross path eg 3, 0, 1
        # cross path is evaluated here while straight path will be evaluated at upper layer
        self.res = max(self.res, first + second + 1)
        
        return first + 1