aboutsummaryrefslogtreecommitdiff
path: root/count_paths_form_palindrome_tree.py
diff options
context:
space:
mode:
Diffstat (limited to 'count_paths_form_palindrome_tree.py')
-rw-r--r--count_paths_form_palindrome_tree.py39
1 files changed, 39 insertions, 0 deletions
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"))