From 001657e7e896dcee47903d25e177018a63e26ebe Mon Sep 17 00:00:00 2001 From: Jack Sangdahl Date: Mon, 14 Oct 2024 12:35:55 -0600 Subject: 2246. longest path with different adjacent characters --- longest_path_diff_adjacent_char.c | 74 +++++++++++++++++++++++++++++++++++ longest_path_diff_adjacent_char.cpp | 48 +++++++++++++++++++++++ longest_path_diff_adjacent_char.py | 48 +++++++++++++++++++++++ longest_path_diff_adjacent_char.rs | 77 +++++++++++++++++++++++++++++++++++++ longest_path_diff_char.cpp | 36 ----------------- longest_path_diff_char.rs | 63 ------------------------------ 6 files changed, 247 insertions(+), 99 deletions(-) create mode 100644 longest_path_diff_adjacent_char.c create mode 100644 longest_path_diff_adjacent_char.cpp create mode 100644 longest_path_diff_adjacent_char.py create mode 100644 longest_path_diff_adjacent_char.rs delete mode 100644 longest_path_diff_char.cpp delete mode 100644 longest_path_diff_char.rs diff --git a/longest_path_diff_adjacent_char.c b/longest_path_diff_adjacent_char.c new file mode 100644 index 0000000..e77ae15 --- /dev/null +++ b/longest_path_diff_adjacent_char.c @@ -0,0 +1,74 @@ +// 2246. Longest Path With Different Adjacent Characters +#include "leetcode.h" + +/* + * you are given a tree (ie. 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 legnth of the longest path in the + * tree such that no pair of adjacnet nodes on the path have the same character + * assigned to them. + */ + +struct node { + bool visited; + int children; + int *adjacent_list; +}; + +void dfs(int curr_node, int *dist, struct node **root, int parent_size, char *s, + int *res) { + int curr_child; + dist[curr_node] = 1; + root[curr_node]->visited = true; + for (int i = 0; i < root[curr_node]->children; i++) { + curr_child = root[curr_node]->adjacent_list[i]; + if (!root[curr_child]->visited) { + dfs(curr_child, dist, root, parent_size, s, res); + if (s[curr_node] != s[curr_child]) { + *res = fmax(*res, dist[curr_node] + dist[curr_child]); + dist[curr_node] = fmax(dist[curr_node], dist[curr_child] + 1); + } + } + } +} + +int longestPath(int *parent, int parentSize, char *s) { + int ans = 1; + int *cnt = (int *)calloc(parentSize, sizeof(int)); + int *dist = (int *)calloc(parentSize, sizeof(int)); + struct node **root = + (struct node **)malloc(parentSize * sizeof(struct node *)); + struct node *curr_node; + for (int i = 1; i < parentSize; i++) { + cnt[parent[i]]++; + cnt[i]++; + } + for (int i = 0; i < parentSize; i++) { + root[i] = (struct node *)malloc(sizeof(struct node)); + root[i]->visited = false; + root[i]->children = 0; + root[i]->adjacent_list = (int *)malloc(cnt[i] * sizeof(int)); + } + for (int i = 1; i < parentSize; i++) { + curr_node = root[parent[i]]; + curr_node->adjacent_list[curr_node->children] = i; + curr_node->children++; + } + dfs(0, dist, root, parentSize, s, &ans); + for (int i = 0; i < parentSize; i++) { + free(root[i]->adjacent_list); + free(root[i]); + } + free(cnt), free(dist), free(root); + return ans; +} + +int main() { + int p1[] = {-1, 0, 0, 1, 1, 2}, p2[] = {-1, 0, 0, 0}; + char *s1 = "abacbe", *s2 = "aabc"; + printf("%d\n", longestPath(p1, ARRAY_SIZE(p1), s1)); // expect: 3 + printf("%d\n", longestPath(p2, ARRAY_SIZE(p2), s2)); // expect: 3 +} diff --git a/longest_path_diff_adjacent_char.cpp b/longest_path_diff_adjacent_char.cpp new file mode 100644 index 0000000..0f60da9 --- /dev/null +++ b/longest_path_diff_adjacent_char.cpp @@ -0,0 +1,48 @@ +// 2246. Longest Path With Different Adjacent Characters +#include "leetcode.h" + +/* + * you are given a tree (ie. 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 legnth of the longest path in the + * tree such that no pair of adjacnet nodes on the path have the same character + * assigned to them. + */ + +class Solution { +public: + int longestPath(vector &parent, string s) { + int n = parent.size(), ans = 1; + queue q; + vector cnt(n), top1(n, 1), top2(n, 1); + for (int i = 1; i < n; ++i) + ++cnt[parent[i]]; + for (int i = 1; i < n; ++i) + if (!cnt[i]) + q.push(i); + while (!q.empty() && q.front()) { + int i = q.front(), p = parent[i]; + q.pop(); + if (int len = 1 + (s[i] != s[p] ? top1[i] : 0); top1[p] <= len) { + top2[p] = top1[p]; + top1[p] = len; + } else + top2[p] = max(top2[p], len); + if (--cnt[p] == 0) { + q.push(p); + ans = max(ans, top1[p] + top2[p] - 1); + } + } + return ans; + } +}; + +int main() { + Solution obj; + vector p1 = {-1, 0, 0, 1, 1, 2}, p2 = {-1, 0, 0, 0}; + printf("%d\n", obj.longestPath(p1, "abacbe")); // expect: 3 + printf("%d\n", obj.longestPath(p2, "aabc")); // expect: 3 +} diff --git a/longest_path_diff_adjacent_char.py b/longest_path_diff_adjacent_char.py new file mode 100644 index 0000000..92f4616 --- /dev/null +++ b/longest_path_diff_adjacent_char.py @@ -0,0 +1,48 @@ +# 2246. Longest Path With Different Adjacent Characters + +""" +you are given a tree (ie. 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 legnth of the longest path in the +tree such that no pair of adjacnet nodes on the path have the same character +assigned to them. +""" + + +class Solution(object): + def longestPath(self, parent, s): + """ + :type parent: List[int] + :type s: str + :rtype: int + """ + ans, n = 0, len(parent) + g = [[] for _ in range(n)] + for i in range(n): + if parent[i] != -1: + g[parent[i]].append(i) + + def dfs(x): + nonlocal ans + l1, l2 = 0, 0 + for i in g[x]: + val = dfs(i) + if s[x] != s[i]: + if val > l2: + l2 = val + if l2 > l1: + l1, l2 = l2, l1 + ans = max(ans, l1 + l2 + 1) + return l1 + 1 + + dfs(0) + return ans + + +if __name__ == "__main__": + obj = Solution() + print(obj.longestPath(parent=[-1, 0, 0, 1, 1, 2], s="abacbe")) + print(obj.longestPath(parent=[-1, 0, 0, 0], s="aabc")) diff --git a/longest_path_diff_adjacent_char.rs b/longest_path_diff_adjacent_char.rs new file mode 100644 index 0000000..b35568c --- /dev/null +++ b/longest_path_diff_adjacent_char.rs @@ -0,0 +1,77 @@ +// 2246. Longest Path With Different Adjacent Characters + +/* + * you are given a tree (ie. 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 legnth of the longest path in the + * tree such that no pair of adjacnet nodes on the path have the same character + * assigned to them. + */ + +use std::cmp::max; +use std::collections::HashMap; +struct Solution; + +static mut res: i32 = 0; +impl Solution { + pub fn longest_path(parent: Vec, s: String) -> i32 { + unsafe { res = 0 } + let mut graph = HashMap::new(); + for (i, &u) in parent.iter().enumerate() { + if u == -1 { + continue; + } + let u = u as usize; + if !graph.contains_key(&u) { + graph.insert(u, vec![]); + } + graph.entry(u).or_insert(vec![]).push(i); + } + let sa: Vec = s.chars().collect(); + Self::dfs(0, &graph, &sa); + let mut ans: i32 = 0; + unsafe { + ans = res; + } + ans + } + fn dfs(root: usize, graph: &HashMap>, s: &Vec) -> i32 { + if !graph.contains_key(&root) { + unsafe { + res = max(res, 1); + } + return 1; + } + let (mut a1, mut a2) = (0, 0); + for &v in graph[&root].iter() { + if s[root] == s[v] { + Self::dfs(v, graph, s); + continue; + } + let curr = Self::dfs(v, graph, s); + if curr >= a1 { + a2 = a1; + a1 = curr; + } else if curr > a2 { + a2 = curr + } + } + unsafe { + res = max(res, a1 + a2 + 1); + } + a1 + 1 + } +} + +fn main() { + let parent1 = vec![-1, 0, 0, 1, 1, 2]; + let parent2 = vec![-1, 0, 0, 0]; + println!( + "{}", + Solution::longest_path(parent1, String::from("abacbe")) + ); //expect: 3 + println!("{}", Solution::longest_path(parent2, String::from("aabc"))); //expect: 3 +} diff --git a/longest_path_diff_char.cpp b/longest_path_diff_char.cpp deleted file mode 100644 index 8eb9878..0000000 --- a/longest_path_diff_char.cpp +++ /dev/null @@ -1,36 +0,0 @@ -#include "leetcode.h" - -class Solution { -public: - int longestPath(vector &parent, string s) { - int n = parent.size(), ans = 1; - queue q; - vector cnt(n), top1(n, 1), top2(n, 1); - for (int i = 1; i < n; ++i) - ++cnt[parent[i]]; - for (int i = 1; i < n; ++i) - if (cnt[i] == 0) - q.push(i); - while (!q.empty() && q.front() != 0) { - int i = q.front(), p = parent[i]; - q.pop(); - if (int len = 1 + (s[i] != s[p] ? top1[i] : 0); top1[p] <= len) { - top2[p] = top1[p]; - top1[p] = len; - } else - top2[p] = max(top2[p], len); - if (--cnt[p] == 0) { - q.push(p); - ans = max(ans, top1[p] + top2[p] - 1); - } - } - return ans; - } -}; - -int main() { - Solution obj; - vector parent1 = {-1, 0, 0, 1, 1, 2}, parent2 = {-1, 0, 0, 0}; - cout << obj.longestPath(parent1, "abacbe") << endl; // expect: 3 - cout << obj.longestPath(parent2, "aabc") << endl; // expect: 3 -} diff --git a/longest_path_diff_char.rs b/longest_path_diff_char.rs deleted file mode 100644 index 4539ad3..0000000 --- a/longest_path_diff_char.rs +++ /dev/null @@ -1,63 +0,0 @@ -use std::collections::HashMap; -use std::cmp::max; -struct Solution; - -static mut res: i32 = 0; -impl Solution { - pub fn longest_path(parent: Vec, s: String) -> i32 { - unsafe { - res = 0 - } - let mut graph = HashMap::new(); - for (i, &u) in parent.iter().enumerate() { - if u == -1 { - continue; - } - let u = u as usize; - if !graph.contains_key(&u) { - graph.insert(u, vec![]); - } - graph.entry(u).or_insert(vec![]).push(i); - } - let sa: Vec = s.chars().collect(); - Self::dfs(0, &graph, &sa); - let mut ans: i32 = 0; - unsafe { - ans = res; - } - ans - } - fn dfs(root: usize, graph: &HashMap>, s: &Vec) -> i32 { - if !graph.contains_key(&root) { - unsafe { - res = max(res, 1); - } - return 1; - } - let (mut a1, mut a2) = (0, 0); - for &v in graph[&root].iter() { - if s[root] == s[v] { - Self::dfs(v, graph, s); - continue; - } - let curr = Self::dfs(v, graph, s); - if curr >= a1 { - a2 = a1; - a1 = curr; - } else if curr > a2 { - a2 = curr - } - } - unsafe { - res = max(res, a1 + a2 + 1); - } - a1 + 1 - } -} - -fn main() { - let parent1 = vec![-1,0,0,1,1,2]; - let parent2 = vec![-1,0,0,0]; - println!("{}", Solution::longest_path(parent1, String::from("abacbe"))); //expect: 3 - println!("{}", Solution::longest_path(parent2, String::from("aabc"))); //expect: 3 -} -- cgit v1.2.3