2246. Longest Path With Different Adjacent Characters Hard

1/**
2 * [2246] Longest Path With Different Adjacent Characters
3 *
4 * 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.
5 * You are also given a string s of length n, where s[i] is the character assigned to node i.
6 * 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.
7 *  
8 * Example 1:
9 * <img alt="" src="https://assets.leetcode.com/uploads/2022/03/25/testingdrawio.png" style="width: 201px; height: 241px;" />
10 * Input: parent = [-1,0,0,1,1,2], s = "abacbe"
11 * Output: 3
12 * 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.
13 * It can be proven that there is no longer path that satisfies the conditions.
14 *
15 * Example 2:
16 * <img alt="" src="https://assets.leetcode.com/uploads/2022/03/25/graph2drawio.png" style="width: 201px; height: 221px;" />
17 * Input: parent = [-1,0,0,0], s = "aabc"
18 * Output: 3
19 * 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.
20 *
21 *  
22 * Constraints:
23 *
24 * n == parent.length == s.length
25 * 1 <= n <= 10^5
26 * 0 <= parent[i] <= n - 1 for all i >= 1
27 * parent[0] == -1
28 * parent represents a valid tree.
29 * s consists of only lowercase English letters.
30 *
31 */
32pub struct Solution {}
33
34// problem: https://leetcode.com/problems/longest-path-with-different-adjacent-characters/
35// discuss: https://leetcode.com/problems/longest-path-with-different-adjacent-characters/discuss/?currentPage=1&orderBy=most_votes&query=
36
37// submission codes start here
38use std::cmp;
39impl Solution {
40    pub fn longest_path(parent: Vec<i32>, s: String) -> i32 {
41        let mut result = 0;
42        // parent -> childens
43        let mut tree: Vec<Vec<usize>> = vec![vec![]; s.len()];
44        for (i, &v) in parent.iter().enumerate().skip(1) {
45            tree[v as usize].push(i);
46        }
47
48        let chs: Vec<_> = s.chars().collect();
49        Self::dfs(&tree, &chs, &mut result, 0);
50        result
51    }
52
53    // return maximun result for the subtree at i which use the node i and is a single hand so parent can use this path
54    fn dfs(tree: &Vec<Vec<usize>>, chs: &Vec<char>, result: &mut i32, i: usize) -> i32 {
55        // max and second_max are the 2 longest path with a single hand
56        let mut max = 0;
57        let mut second_max = 0;
58        let node_val = chs[i];
59        for &child in tree[i].iter() {
60            let child_max = Self::dfs(&tree, &chs, result, child);
61            if node_val == chs[child] {
62                continue;
63            }
64            if child_max > max {
65                second_max = max;
66                max = child_max;
67            } else if child_max > second_max {
68                second_max = child_max;
69            }
70        }
71        max += 1;
72        *result = cmp::max(*result, max + second_max);
73        max
74    }
75}
76
77// submission codes end
78
79#[cfg(test)]
80mod tests {
81    use super::*;
82
83    #[test]
84    fn test_2246() {
85        assert_eq!(
86            3,
87            Solution::longest_path(vec![-1, 0, 0, 1, 1, 2], "abacbe".to_owned())
88        );
89        assert_eq!(
90            3,
91            Solution::longest_path(vec![-1, 0, 0, 0], "aabc".to_owned())
92        );
93    }
94}
95