leetcode-solution/Python/2246-longest-path-with-different-adjacent-characters.py at main · hogan-tech/leetcode-solution · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
# time complexity: O(n)
# space complexity: O(n)
from collections import deque
from typing import List


class Solution:
    def longestPath(self, parent: List[int], s: str) -> int:
        n = len(parent)
        indegree = [0] * n
        for node in range(1, n):
            indegree[parent[node]] += 1

        queue = deque()
        longestChains = [[0, 0] for _ in range(n)]
        longestPath = 1

        for node in range(n):
            if indegree[node] == 0:
                queue.append(node)
                longestChains[node][0] = 1

        while queue:
            currentNode = queue.popleft()
            parentNode = parent[currentNode]

            if parentNode != -1:
                longestChainFromCurr = longestChains[currentNode][0]

                if s[currentNode] != s[parentNode]:
                    if longestChainFromCurr > longestChains[parentNode][0]:
                        longestChains[parentNode][1] = longestChains[parentNode][0]
                        longestChains[parentNode][0] = longestChainFromCurr
                    elif longestChainFromCurr > longestChains[parentNode][1]:
                        longestChains[parentNode][1] = longestChainFromCurr

                longestPath = max(
                    longestPath, longestChains[parentNode][0] + longestChains[parentNode][1] + 1)

                indegree[parentNode] -= 1
                if indegree[parentNode] == 0:
                    longestChains[parentNode][0] += 1
                    queue.append(parentNode)
        return longestPath


parent = [-1, 0, 0, 1, 1, 2]
s = "abacbe"
print(Solution().longestPath(parent, s))
parent = [-1, 0, 0, 0]
s = "aabc"
print(Solution().longestPath(parent, s))