Welcome to Subscribe On Youtube
Formatted question description: https://leetcode.ca/all/2246.html
2246. Longest Path With Different Adjacent Characters
- Difficulty: Hard.
- Related Topics: Array, String, Tree, Depth-First Search, Graph, Topological Sort.
- Similar Questions: Diameter of Binary Tree, Longest Univalue Path, Choose Edges to Maximize Score in a Tree.
Problem
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
-
class Solution { public int longestPath(int[] parent, String s) { // for first max length int[] first = new int[s.length()]; Arrays.fill(first, 0); // for second max length int[] second = new int[s.length()]; Arrays.fill(second, 0); // for number of children for this node int[] children = new int[s.length()]; Arrays.fill(children, 0); for (int i = 1; i != s.length(); i++) { // calculate all children for each node children[parent[i]]++; } // for traversal from leafs to root LinkedList<Integer> st = new LinkedList<>(); // put all leafs for (int i = 1; i != s.length(); i++) { if (children[i] == 0) { st.add(i); } } // traversal from leafs to root while (!st.isEmpty()) { // fetch current node int i = st.pollLast(); // if we in root - ignore it if (i == 0) { continue; } if (--children[parent[i]] == 0) { // decrease number of children by parent node and if number of children st.add(parent[i]); } // is equal 0 - our parent became a leaf // if letters isn't equal if (s.charAt(parent[i]) != s.charAt(i)) { // fetch maximal path from node int maxi = 1 + Math.max(first[i], second[i]); // and update maximal first and second path from parent if (maxi >= first[parent[i]]) { second[parent[i]] = first[parent[i]]; first[parent[i]] = maxi; } else if (second[parent[i]] < maxi) { second[parent[i]] = maxi; } } } // fetch answer int ans = 0; for (int i = 0; i != s.length(); i++) { ans = Math.max(ans, first[i] + second[i]); } return ans + 1; } }
-
Todo
-
# 2246. Longest Path With Different Adjacent Characters # https://leetcode.com/problems/longest-path-with-different-adjacent-characters/ class Solution: def longestPath(self, parent: List[int], s: str) -> int: n = len(parent) graph = defaultdict(list) res = 0 for x, y in enumerate(parent): if y == -1 or s[x] == s[y]: continue graph[y].append(x) graph[x].append(y) @cache def go(node, prev): nonlocal res path = [1] for nei in graph[node]: if nei != prev: path.append(go(nei, node) + 1) path.sort(reverse = 1) if len(path) == 1: res = max(res, path[0]) else: res = max(res, path[0] + path[1] - 1) return path[0] for i in range(n): go(i, -1) return res
Explain:
nope.
Complexity:
- Time complexity : O(n).
- Space complexity : O(n).