You are given a tree (i.e. a connected, undirected graph that has no cycles) rooted at node 0
consisting of n
nodes numbered from 0
to n - 1
. The tree is represented by a 0-indexed array parent
of size n
, where parent[i]
is the parent of node i
. Since node 0
is the root, parent[0] == -1
.
You are also given a string s
of length n
, where s[i]
is the character assigned to node i
.
Return the length of the longest path in the tree such that no pair of adjacent nodes on the path have the same character assigned to them.
Example 1:
Input: parent = [-1,0,0,1,1,2], s = "abacbe"
Output: 3
Explanation: The longest path where each two adjacent nodes have different characters in the tree is the path: 0 -> 1 -> 3. The length of this path is 3, so 3 is returned.
It can be proven that there is no longer path that satisfies the conditions.
Example 2:
Input: parent = [-1,0,0,0], s = "aabc"
Output: 3
Explanation: The longest path where each two adjacent nodes have different characters is the path: 2 -> 0 -> 3. The length of this path is 3, so 3 is returned.
Constraints:
-
n == parent.length == s.length
-
1 <= n <= 105
-
0 <= parent[i] <= n - 1
for alli >= 1
-
parent[0] == -1
-
parent
represents a valid tree. -
s
consists of only lowercase English letters.
SOLUTION:
from collections import defaultdict
class Solution:
def longest(self, tree, root, s, branch):
l = 1
key = (root, branch)
if key in self.cache:
return self.cache[key]
if branch:
best = 0
sbest = 0
for j in tree[root]:
if s[root] != s[j]:
currl = self.longest(tree, j, s, False)
sbest, best = sorted([sbest, best, currl])[-2:]
l = max(l, 1 + best + sbest)
self.cache[key] = l
return l
for j in tree[root]:
if s[root] != s[j]:
currl = self.longest(tree, j, s, False)
l = max(l, 1 + currl)
self.cache[key] = l
return l
def longestPath(self, parent: List[int], s: str) -> int:
n = len(s)
self.cache = {}
tree = defaultdict(list)
for i in range(n):
if parent[i] != -1:
tree[parent[i]].append(i)
mpath = 0
for i in range(n):
l = self.longest(tree, i, s, True)
mpath = max(mpath, l)
return mpath
Top comments (0)