23.01.13 Today’s Leetcode

2246. Longest Path With Different Adjacent Characters (hard)

1. Fail

import copy

class Solution:
    def dfs(self, parent, s, dp, check, current):
        n = len(parent)
        for i in range(1, n):
            if parent[i] == current:
                dp[i] = copy.deepcopy(dp[current])
                dp[i][s[i]] = dp[i].get(s[i], 0) + 1
                if dp[i][s[i]] >= 2:
                    check[i] = False
                self.dfs(parent, s, dp, check, i)


    def longestPath(self, parent: List[int], s: str) -> int:
        n = len(parent)
        dp = [{}] * n
        check = [True] * n
        dp[0][s[0]] = 1
        self.dfs(parent, s, dp, check, 0)
        res = 0
        for i, p in enumerate(check):
            if p:
                print(i, dp[i])
                res = max(res, len(dp[i]))
        return res

1. Fail (with Tree re-format)

import copy

class Solution:

    def longestPath(self, parent: List[int], s: str) -> int:
        n = len(parent)
        tree = defaultdict(list)
        for i in range(1, n):
            cur, par = i, parent[i]
            if s[cur] != s[par]:
                tree[cur].append(par)
                tree[par].append(cur)

        res = 0

        def dfs(cur, par, length):
            nonlocal res
            res = max(res, length)

            for node in tree[cur]:
                if node != par:
                    dfs(node, cur, length + 1)

        for i in range(n):
            dfs(i, -1, 1)

        return res

1. Solution

class Solution:
    def longestPath(self, parent: List[int], s: str) -> int:
        # Construct the tree using the parent list.
        tree = defaultdict(list)
        for end,start in enumerate(parent):
            tree[start].append(end)
        
        # Store the longest path
        # It is updated in dfs
        res = 1
        
        # dfs will return the longest valid path starting from this node in the sub-tree rooted at this node.
        def dfs(node):
            nonlocal res
            
            # While examing the children, 
            # We want to keep track of the 2 longest paths starting from this node,
            # So that we can compute the longest path going through this node 
            # in the sub-tree rooted at this node.
            max1 = max2 = 0

            for nei in tree[node]:
                neiL = dfs(nei)
                # This condition makes sure the path is valid.
                if s[nei] != s[node]:
                    # Update the length of the top two longest paths.
                    if neiL > max1:
                        max2 = max1
                        max1 = neiL
                    elif neiL > max2:
                        max2 = neiL
            
            # Update the result.
            # Again, max1+max2+1 means the length of the longest valid path 
            # going through this node in the sub-tree rooted at this node.
            res = max(res, max1+max2+1)
            
            # Adding 1 for the current node
            return max1+1
        
        dfs(0)
        return res