2791. Count Paths That Can Form a Palindrome in a Tree
Asked at Uber, Goldman Sachs
Difficulty
Hard
Time
O(n * 26)
Space
O(n)
Pattern
Hash Table
Companies
2
Problem
You are given a tree with n nodes numbered 0 to n-1, rooted at node 0. The tree comes as an array parent, where parent[i] is the parent of node i, and parent[0] == -1 because node 0 is the root.
You also get a string s of length n. The character s[i] is written on the edge between node i and its parent. The value s[0] has no edge, so you can ignore it.
Count the number of pairs of nodes (u, v) with u < v such that the characters on the path from u to v can be rearranged into a palindrome. A palindrome reads the same forwards and backwards. Note: you do not need the path itself to be a palindrome — you only need its letters to be rearrangeable into one.
Key rule that decides the answer: a set of letters can be rearranged into a palindrome exactly when at most one letter appears an odd number of times. So for each path you only care about which letters have odd counts, not their order.
Which paths can be rearranged into a palindrome
Constraints
- ●
n == parent.length == s.length - ●
1 <= n <= 10^5 - ●
0 <= parent[i] <= n - 1 for all i >= 1 - ●
parent[0] == -1 - ●
parent represents a valid tree - ●
s consists of only lowercase English letters
Examples
parent = [-1,0,0,1,1,2], s = "acaabc"8parent = [-1,0,0,0,0], s = "aaaaa"10Asked At
2 companies| Company | Difficulty | |
|---|---|---|
| Uber | Hard | View all Uber questions → |
| Goldman Sachs | Hard | View all Goldman Sachs questions → |
How to Think About It
Key insight: a path forms a palindrome iff at most one character has an odd count. Represent the path as a 26-bit mask (bit i set if character i appears odd times). The path mask from u to v is mask[u] XOR mask[v] XOR (1 << s[root]).
Compute masks via DFS from root: mask[root] = 1 << s[root]. For child c of node p: mask[c] = mask[p] ^ (1 << s[c]). The XOR accumulates odd-count flips along the path.
Path mask between u and v: mask[u] XOR mask[v]. For a palindrome, popcount(mask[u] XOR mask[v]) <= 1. This means the masks are either equal (0 bits differ) or differ in exactly 1 bit.
Count pairs: for each mask value, count pairs of nodes with the same mask (C(cnt,2)) plus pairs differing in exactly 1 bit (cnt[mask] * cnt[mask ^ (1<<i)] for each bit i). Divide cross-bit pairs by 2 to avoid double-counting.
Use a hash map to count mask frequencies during DFS. After processing all nodes, iterate the map to count pairs.
Optimal Approach
Step 1: Build adjacency list from parent array.
Step 2: DFS from root to compute mask for each node: mask[child] = mask[parent] XOR (1 << s[child]).
Step 3: Count mask frequencies using a hash map.
Step 4: For each mask in the map:
- Same-mask pairs: add C(cnt, 2) = cnt*(cnt-1)/2.
- Cross-bit pairs: for each bit i (0-25), if mask ^ (1<<i) exists in map and mask < mask^(1<<i), add cnt[mask] * cnt[mask^(1<<i)].
Step 5: Return total.
Walkthrough for n=3, parent=[0,0,0], s="abc":
- Root=0, mask[0]=1 (a). Children: 1 mask=1^2=3 (b), 2 mask=1^4=5 (c).
- Masks: {1:1, 3:1, 5:1}. Same-mask: 0 pairs. Cross-bit: 1^3=2 (1 bit) -> 11=1. 1^5=4 (1 bit) -> 11=1. 3^5=6 (2 bits) -> 0. Total: 2.
Time: O(n * 26) for DFS and mask counting. Space: O(n) for masks and hash map.
XOR masks and pair counting
What Trips People Up in Real Interviews
Forgetting that the path mask is just mask[u] XOR mask[v], not mask[u] XOR mask[v] XOR something extra. The XOR naturally handles the parity of all characters on the path.
Double-counting pairs. Each pair (u,v) should be counted once. When iterating masks, use pairs where mask1 < mask2 for cross-bit pairs, and C(cnt,2) for same-mask pairs.
Confusing path with root-to-node. The path between any two nodes u and v goes through their LCA. The XOR trick works regardless of the LCA because XOR cancels out the common prefix.
Missing that C(cnt,2) = cnt*(cnt-1)/2 for same-mask pairs. Do not use cnt*cnt which includes self-pairs.
Forgetting that single-node paths (u==v) are valid palindromes (1 character). The problem asks for pairs of distinct nodes, so self-pairs are excluded by C(cnt,2).
Solution Code
O(n * 26) timefrom collections import defaultdict
class Solution:
def countPalindromicPaths(self, parent, s):
n = len(parent)
g = [[] for _ in range(n)]
for i in range(1, n):
g[parent[i]].append(i)
g[i].append(parent[i])
mask = [0] * n
stack = [0]
mask[0] = 1 << (ord(s[0]) - 97)
visited = [False] * n
visited[0] = True
order = [0]
while stack:
u = stack.pop()
for v in g[u]:
if not visited[v]:
visited[v] = True
mask[v] = mask[u] ^ (1 << (ord(s[v]) - 97))
stack.append(v)
order.append(v)
cnt = defaultdict(int)
for m in mask:
cnt[m] += 1
ans = 0
for m, c in cnt.items():
ans += c * (c - 1) // 2
for b in range(26):
t = m ^ (1 << b)
if t in cnt and m < t:
ans += c * cnt[t]
return ansFrequently Asked Questions
What is the Count Paths That Can Form a Palindrome in a Tree problem?
Given a tree with n nodes (0 to n-1), parent array where parent[i] is the parent of node i (0 for root), and a string s of lowercase letters where s[i] is the character at node i. Count the number of unordered pairs of nodes (u,v) such that the path from u to v contains characters that can be rearranged into a palindrome.
How do you solve Count Paths That Can Form a Palindrome in a Tree?
The optimal approach runs in O(n * 26) time and O(n) space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.
What companies ask Count Paths That Can Form a Palindrome in a Tree?
Count Paths That Can Form a Palindrome in a Tree is asked at Uber, Goldman Sachs. It is a hard difficulty problem.
What are common mistakes on Count Paths That Can Form a Palindrome in a Tree?
- Forgetting that the path mask is just mask[u] XOR mask[v], not mask[u] XOR mask[v] XOR something extra. The XOR naturally handles the parity of all characters on the path.
- Double-counting pairs. Each pair (u,v) should be counted once. When iterating masks, use pairs where mask1 < mask2 for cross-bit pairs, and C(cnt,2) for same-mask pairs.
- Confusing path with root-to-node. The path between any two nodes u and v goes through their LCA. The XOR trick works regardless of the LCA because XOR cancels out the common prefix.
- Missing that C(cnt,2) = cnt*(cnt-1)/2 for same-mask pairs. Do not use cnt*cnt which includes self-pairs.
- Forgetting that single-node paths (u==v) are valid palindromes (1 character). The problem asks for pairs of distinct nodes, so self-pairs are excluded by C(cnt,2).