aboutsummaryrefslogtreecommitdiff
path: root/longest_path_diff_adjacent_char.c
diff options
context:
space:
mode:
Diffstat (limited to 'longest_path_diff_adjacent_char.c')
-rw-r--r--longest_path_diff_adjacent_char.c74
1 files changed, 74 insertions, 0 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
+}