Count Paths That Can Form a Palindrome in a Tree
Asked at Uber
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.
Asked At
| Company | Difficulty | |
|---|---|---|
| Uber | Hard | View all Uber 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.
Visual walkthrough for path a-b-c with s="abc": mask[a]=1, mask[b]=1^2=3, mask[c]=3^4=7. a-b: mask[0]^mask[1]=1^3=2 (1 bit set -> palindrome). b-c: 3^7=4 (1 bit -> palindrome). a-c: 1^7=6 (2 bits -> not palindrome).
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.
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
from 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 is described in detail above, including step-by-step walkthroughs, complexity analysis, and solution code in Python. Scroll up to the "Optimal Approach" section.
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. 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).