aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorJack Sangdahl <[email protected]>2024-10-06 21:57:58 -0600
committerJack Sangdahl <[email protected]>2024-10-06 21:58:06 -0600
commitb9c16a156eff8ebe6627a0869fdd6d360aec9bc5 (patch)
treea683212bc75ff3fba193586f76ad8a17d4772273
parente4e9e626e5b5a9659510d4b71a742f14e4580079 (diff)
downloadleetcode-b9c16a156eff8ebe6627a0869fdd6d360aec9bc5.tar.gz
leetcode-b9c16a156eff8ebe6627a0869fdd6d360aec9bc5.zip
2791. count paths that can form a palindrome in a tree
-rw-r--r--count_paths_form_palindrome_tree.c82
-rw-r--r--count_paths_form_palindrome_tree.py39
2 files changed, 121 insertions, 0 deletions
diff --git a/count_paths_form_palindrome_tree.c b/count_paths_form_palindrome_tree.c
new file mode 100644
index 0000000..07c8623
--- /dev/null
+++ b/count_paths_form_palindrome_tree.c
@@ -0,0 +1,82 @@
+// 2791. Count Paths That Can Form a Palindrome in a Tree
+#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 the edge between 'i' and 'parent[i]'. 's[0]' can be ignored. return the
+ * number of pairs of nodes '(u, v)' such that 'u < v' and the characters
+ * assigned to edges on the path from 'u' to 'v' can rearranged to form a
+ * palindrome
+ */
+
+void fill_table(int *parent, int parentSize, char *s, int *dp, int *filled,
+ int k, int *hash_table, int *hash_vals) {
+ if (filled[k])
+ return;
+ if (!k) {
+ filled[k] = 1;
+ hash_table[0] = 1;
+ hash_vals[0] = 0;
+ return;
+ }
+ fill_table(parent, parentSize, s, dp, filled, parent[k], hash_table,
+ hash_vals);
+ int mask = dp[parent[k]] ^ (1 << (s[k] - 97));
+ dp[k] = mask;
+ filled[k] = 1;
+ int kk = parentSize * 2, idx = mask % kk;
+ while (hash_vals[idx] != -1 && hash_vals[idx] != mask) {
+ idx++;
+ if (idx >= kk)
+ idx -= kk;
+ }
+ if (hash_vals[idx] == -1)
+ hash_vals[idx] = mask;
+ hash_table[idx]++;
+}
+
+long long countPalindromePaths(int *parent, int parentSize, char *s) {
+ int kk = parentSize * 2, n = parentSize;
+ int *dp = (int *)calloc(n, sizeof(int));
+ int *filled = (int *)calloc(n, sizeof(int));
+ int *hash_table = (int *)calloc(kk, sizeof(int));
+ int *hash_vals = (int *)malloc(kk * sizeof(int));
+ for (int i = 0; i < kk; i++)
+ hash_vals[i] = -1;
+ for (int k = 0; k < n; k++)
+ fill_table(parent, parentSize, s, dp, filled, k, hash_table, hash_vals);
+ long long cnt = 0;
+ for (int k = 0; k < n; k++) {
+ int mask = dp[k];
+ int idx = mask % kk;
+ while (hash_vals[idx] != -1 && hash_vals[idx] != mask) {
+ idx++;
+ if (idx >= kk)
+ idx -= kk;
+ }
+ cnt += hash_table[idx] - 1;
+ for (int j = 0; j < 26; j++) {
+ int new_mask = mask ^ (1 << j);
+ int new_idx = new_mask % kk;
+ while (hash_vals[new_idx] != -1 && hash_vals[new_idx] != new_mask) {
+ new_idx++;
+ if (new_idx >= kk)
+ new_idx -= kk;
+ }
+ cnt += hash_table[new_idx];
+ }
+ }
+ free(dp), free(filled), free(hash_table), free(hash_vals);
+ return cnt;
+}
+
+int main() {
+ int p1[] = {-1, 0, 0, 1, 1, 2}, p2[] = {-1, 0, 0, 0, 0};
+ char *s1 = "acaabc", *s2 = "aaaaa";
+ printf("%lld\n", countPalindromePaths(p1, ARRAY_SIZE(p1), s1)); // expect: 8
+ printf("%lld\n", countPalindromePaths(p2, ARRAY_SIZE(p2), s2)); // expect: 10
+}
diff --git a/count_paths_form_palindrome_tree.py b/count_paths_form_palindrome_tree.py
new file mode 100644
index 0000000..e4740d8
--- /dev/null
+++ b/count_paths_form_palindrome_tree.py
@@ -0,0 +1,39 @@
+# 2791. Count Paths That Can Form a Palindrome in a Tree
+from collections import Counter
+
+"""
+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 the edge between 'i' and 'parent[i]'. 's[0]' can be ignored. return the
+number of pairs of nodes '(u, v)' such that 'u < v' and the characters
+assigned to edges on the path from 'u' to 'v' can rearranged to form a
+palindrome
+"""
+
+
+class Solution(object):
+ def countPalindromePaths(self, parent, s):
+ """
+ :type parent: List[int]
+ :type s: str
+ :rtype: int
+ """
+
+ def f(i):
+ return f(parent[i]) ^ (1 << (ord(s[i]) - ord("a"))) if i else 0
+
+ cnt, ans = Counter(), 0
+ for i in range(len(parent)):
+ mask = f(i)
+ ans += cnt[mask] + sum(cnt[mask ^ (1 << j)] for j in range(26))
+ cnt[mask] += 1
+ return ans
+
+
+if __name__ == "__main__":
+ obj = Solution()
+ print(obj.countPalindromePaths(parent=[-1, 0, 0, 1, 1, 2], s="acaabc"))
+ print(obj.countPalindromePaths(parent=[-1, 0, 0, 0, 0], s="aaaaa"))