Count Palindromic Ancestor Paths
Learn this problem
UberFULLTIMEOAProblem statement
You are given a rooted tree with nodes numbered from 0 to n - 1. The root is node 0. For every node i, parent[i] is its parent, with parent[0] = -1. The character labels.charAt(i) labels node i.
For each node u in queries, count the ancestors v of u, including u itself, such that the multiset of labels on the inclusive path from v to u can be rearranged into a palindrome.
Return the counts in query order. A multiset can form a palindrome exactly when at most one character has an odd frequency.
Function
countPalindromicAncestorPaths(parent: int[], labels: String, queries: int[]) → int[]Examples
Example 1
parent = [-1,0,0,1,1,2]labels = "abacba"queries = [3,4,5]return = [1,3,3]For node 3, only the one-node path is valid. For node 4, the paths beginning at nodes 0, 1, and 4 are all palindromic after rearrangement. All three ancestors of node 5 are valid as well.
Example 2
parent = [-1,0,1,2]labels = "aaaa"queries = [0,3]return = [1,4]Every path contains only a, so every ancestor of each queried node is valid.
Example 3
parent = [-1,0,1]labels = "abc"queries = [2]return = [1]The one-node path containing c is valid. The longer paths have two or three odd character counts.
Constraints
1 <= parent.length == labels.length <= 200000.parent[0] = -1, and fori > 0,0 <= parent[i] < i.labelscontains only lowercase English letters.1 <= queries.length <= 200000.- Every query is a valid node index; query nodes may repeat.