aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--longest_path_diff_adjacent_char.c74
-rw-r--r--longest_path_diff_adjacent_char.cpp48
-rw-r--r--longest_path_diff_adjacent_char.py48
-rw-r--r--longest_path_diff_adjacent_char.rs (renamed from longest_path_diff_char.rs)32
-rw-r--r--longest_path_diff_char.cpp36
5 files changed, 193 insertions, 45 deletions
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<int> &parent, string s) {
+ int n = parent.size(), ans = 1;
+ queue<int> q;
+ vector<int> 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<int> 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_char.rs b/longest_path_diff_adjacent_char.rs
index 4539ad3..b35568c 100644
--- a/longest_path_diff_char.rs
+++ b/longest_path_diff_adjacent_char.rs
@@ -1,13 +1,24 @@
-use std::collections::HashMap;
+// 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;
+static mut res: i32 = 0;
impl Solution {
pub fn longest_path(parent: Vec<i32>, s: String) -> i32 {
- unsafe {
- res = 0
- }
+ unsafe { res = 0 }
let mut graph = HashMap::new();
for (i, &u) in parent.iter().enumerate() {
if u == -1 {
@@ -56,8 +67,11 @@ impl Solution {
}
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
+ 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<int> &parent, string s) {
- int n = parent.size(), ans = 1;
- queue<int> q;
- vector<int> 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<int> 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
-}