Count Paths That Can Form a Palindrome in a Tree
Count Paths That Can Form a Palindrome in a Tree is a hard bit manipulation problem solved with the xor basics pattern.
The best approach, optimal (root masks + hash map), runs in O(26 · n) time and O(n) space.
Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (walk from every node) up.
Problem
You get a tree with n nodes numbered 0 to n - 1, rooted at node 0, described by an array parent (parent[0] == -1). For every i >= 1 there is an edge between parent[i] and i, and that edge is labelled with the letter s[i]. The character s[0] has no edge and is ignored.
Count the pairs of nodes (u, v) with u < v such that the letters on the edges of the path between u and v can be rearranged into a palindrome. An empty or one-letter sequence is a palindrome too.
Examples
Example 1
- Input
parent = [-1, 0, 0, 1, 1], s = "xabab"- Output
7- Why
- Edges: 0-1 'a', 0-2 'b', 1-3 'a', 1-4 'b'. Of the 10 pairs, only (1, 2), (0, 4) and (3, 4) read one 'a' and one 'b', which cannot be a palindrome.
Example 2
- Input
parent = [-1, 0, 1, 2], s = "zabc"- Output
3- Why
- The tree is a chain 0-1-2-3 with letters a, b, c. Only the three single-edge paths work; any longer path has two different letters.
Example 3
- Input
parent = [-1, 0, 0, 0], s = "qmmm"- Output
6- Why
- Every edge is 'm', so every path reads "m" or "mm". All 6 pairs count.
Constraints
n == parent.length == s.length1 <= n <= 10^5parent[0] == -1, and fori >= 1,0 <= parent[i] < n; the edges form a tree rooted at 0.scontains only lowercase English letters;s[0]is ignored.
Solve it here
Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.
Your own testcases: Run checks these, and the expected output comes from our reference solution.
My submissions
Nothing yet. Every Run and Submit you make while signed in shows up here.
| When | Result | Tests | Runtime | Your time | Type |
|---|
Run checks the testcases above (3 examples, or your own). Submit also runs 13 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.
Solutions
Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.
| Approach | Time | Space |
|---|---|---|
| Brute force (walk from every node) | O(n²) | O(n) |
| Optimal (root masks + hash map) | O(26 · n) | O(n) |
1Brute force (walk from every node)
O(n²)Each of the n traversals visits all n nodes.O(n)The adjacency list, the visited array and the stack are all O(n).Treat the tree as an undirected graph. From every node u, run a traversal that carries the parity mask of the path so far. Each node v > u that is reached with a mask that has at most one bit set forms a valid pair.
- Build an adjacency list where each edge stores its letter.
- For each u, traverse from u with an explicit stack, carrying the mask of the path from u.
- For every visited v with v > u, add 1 if mask & (mask - 1) == 0.
class Solution {
public long countPalindromePaths(List<Integer> parent, String s) {
int n = parent.size();
List<List<int[]>> adj = new ArrayList<>();
for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
for (int i = 1; i < n; i++) {
int p = parent.get(i), bit = 1 << (s.charAt(i) - 'a');
adj.get(p).add(new int[] { i, bit });
adj.get(i).add(new int[] { p, bit });
}
long count = 0;
for (int u = 0; u < n; u++) {
boolean[] seen = new boolean[n];
Deque<int[]> stack = new ArrayDeque<>();
stack.push(new int[] { u, 0 });
seen[u] = true;
while (!stack.isEmpty()) {
int[] cur = stack.pop();
int v = cur[0], mask = cur[1];
if (v > u && (mask & (mask - 1)) == 0) count++;
for (int[] e : adj.get(v)) {
if (!seen[e[0]]) {
seen[e[0]] = true;
stack.push(new int[] { e[0], mask ^ e[1] });
}
}
}
}
return count;
}
}class Solution:
def countPalindromePaths(self, parent: List[int], s: str) -> int:
n = len(parent)
adj = [[] for _ in range(n)]
for i in range(1, n):
bit = 1 << (ord(s[i]) - 97)
adj[parent[i]].append((i, bit))
adj[i].append((parent[i], bit))
count = 0
for u in range(n):
seen = [False] * n
seen[u] = True
stack = [(u, 0)]
while stack:
v, mask = stack.pop()
if v > u and mask & (mask - 1) == 0:
count += 1
for w, bit in adj[v]:
if not seen[w]:
seen[w] = True
stack.append((w, mask ^ bit))
return countclass Solution {
public:
long long countPalindromePaths(vector<int>& parent, string s) {
int n = parent.size();
vector<vector<pair<int, int>>> adj(n);
for (int i = 1; i < n; i++) {
int bit = 1 << (s[i] - 'a');
adj[parent[i]].push_back({i, bit});
adj[i].push_back({parent[i], bit});
}
long long count = 0;
for (int u = 0; u < n; u++) {
vector<bool> seen(n, false);
vector<pair<int, int>> stack = {{u, 0}};
seen[u] = true;
while (!stack.empty()) {
auto [v, mask] = stack.back();
stack.pop_back();
if (v > u && (mask & (mask - 1)) == 0) count++;
for (auto& [w, bit] : adj[v]) {
if (!seen[w]) {
seen[w] = true;
stack.push_back({w, mask ^ bit});
}
}
}
}
return count;
}
};function countPalindromePaths(parent, s) {
const n = parent.length;
const adj = Array.from({ length: n }, () => []);
for (let i = 1; i < n; i++) {
const bit = 1 << (s.charCodeAt(i) - 97);
adj[parent[i]].push([i, bit]);
adj[i].push([parent[i], bit]);
}
let count = 0;
for (let u = 0; u < n; u++) {
const seen = new Array(n).fill(false);
seen[u] = true;
const stack = [[u, 0]];
while (stack.length > 0) {
const [v, mask] = stack.pop();
if (v > u && (mask & (mask - 1)) === 0) count++;
for (const [w, bit] of adj[v]) {
if (!seen[w]) {
seen[w] = true;
stack.push([w, mask ^ bit]);
}
}
}
}
return count;
}2Optimal (root masks + hash map)
O(26 · n)Each node does 27 hash map lookups.O(n)The child lists, the masks and the frequency map each hold at most n entries.Compute mask[v], the parity of letters on the path from the root to v, with an iterative traversal. For a pair (u, v) the letters on their path have parity mask[u] ^ mask[v]. Process nodes one by one and, for each, count earlier nodes with the same mask or with one of the 26 masks that differ in a single bit, using a hash map of mask frequencies.
- Build child lists and compute mask[v] = mask[parent[v]] ^ (1 << (s[v] - 'a')) in BFS order from the root.
- Walk the nodes; for each mask m add freq[m] and freq[m ^ (1 << b)] for b in 0..25.
- Then increment freq[m].
class Solution {
public long countPalindromePaths(List<Integer> parent, String s) {
int n = parent.size();
List<List<Integer>> children = new ArrayList<>();
for (int i = 0; i < n; i++) children.add(new ArrayList<>());
for (int i = 1; i < n; i++) children.get(parent.get(i)).add(i);
int[] mask = new int[n];
int[] queue = new int[n];
int head = 0, tail = 0;
queue[tail++] = 0;
while (head < tail) {
int u = queue[head++];
for (int v : children.get(u)) {
mask[v] = mask[u] ^ (1 << (s.charAt(v) - 'a'));
queue[tail++] = v;
}
}
Map<Integer, Integer> freq = new HashMap<>();
long count = 0;
for (int v = 0; v < n; v++) {
int m = mask[v];
count += freq.getOrDefault(m, 0);
for (int b = 0; b < 26; b++) {
count += freq.getOrDefault(m ^ (1 << b), 0);
}
freq.merge(m, 1, Integer::sum);
}
return count;
}
}class Solution:
def countPalindromePaths(self, parent: List[int], s: str) -> int:
n = len(parent)
children = [[] for _ in range(n)]
for i in range(1, n):
children[parent[i]].append(i)
mask = [0] * n
queue = [0]
for u in queue: # the list grows while we iterate: BFS order
for v in children[u]:
mask[v] = mask[u] ^ (1 << (ord(s[v]) - 97))
queue.append(v)
freq = {}
count = 0
bits = [1 << b for b in range(26)]
for m in mask:
count += freq.get(m, 0)
for bit in bits:
count += freq.get(m ^ bit, 0)
freq[m] = freq.get(m, 0) + 1
return countclass Solution {
public:
long long countPalindromePaths(vector<int>& parent, string s) {
int n = parent.size();
vector<vector<int>> children(n);
for (int i = 1; i < n; i++) children[parent[i]].push_back(i);
vector<int> mask(n, 0), queue;
queue.reserve(n);
queue.push_back(0);
for (int h = 0; h < (int)queue.size(); h++) {
int u = queue[h];
for (int v : children[u]) {
mask[v] = mask[u] ^ (1 << (s[v] - 'a'));
queue.push_back(v);
}
}
unordered_map<int, int> freq;
long long count = 0;
for (int v = 0; v < n; v++) {
int m = mask[v];
auto it = freq.find(m);
if (it != freq.end()) count += it->second;
for (int b = 0; b < 26; b++) {
auto jt = freq.find(m ^ (1 << b));
if (jt != freq.end()) count += jt->second;
}
freq[m]++;
}
return count;
}
};function countPalindromePaths(parent, s) {
const n = parent.length;
const children = Array.from({ length: n }, () => []);
for (let i = 1; i < n; i++) children[parent[i]].push(i);
const mask = new Array(n).fill(0);
const queue = [0];
for (let h = 0; h < queue.length; h++) {
const u = queue[h];
for (const v of children[u]) {
mask[v] = mask[u] ^ (1 << (s.charCodeAt(v) - 97));
queue.push(v);
}
}
const freq = new Map();
let count = 0;
for (let v = 0; v < n; v++) {
const m = mask[v];
count += freq.get(m) || 0;
for (let b = 0; b < 26; b++) {
count += freq.get(m ^ (1 << b)) || 0;
}
freq.set(m, (freq.get(m) || 0) + 1);
}
return count;
}Edge cases to test
- A single node: there are no pairs, answer 0
- A long chain (depth 10^5), which breaks naive recursion
- Pairs where one node is an ancestor of the other
- All edges carrying the same letter: every pair counts, n(n - 1) / 2, which needs a 64-bit result
Hints
Hint 1
A multiset of letters can be rearranged into a palindrome exactly when at most one letter has an odd count. Store the odd/even state of all 26 letters in one 26-bit mask.
Hint 2
Let mask[v] be the parity mask of the path from the root to v. The letters on the path u-v have parity mask[u] XOR mask[v], because the shared part above their meeting point cancels.
Hint 3
Count pairs whose masks are equal or differ in exactly one bit, using a hash map from mask to how many nodes have it.
FAQ
What is the best time complexity for Count Paths That Can Form a Palindrome in a Tree?
Optimal (root masks + hash map) runs in O(26 · n) time and O(n) extra space. Each node does 27 hash map lookups.
Which pattern does Count Paths That Can Form a Palindrome in a Tree use?
It is a bit manipulation problem that uses the xor basics pattern. Other problems with the same pattern: Swap two numbers, Hamming Distance, XOR Operation in an Array.
Is there a brute force solution for Count Paths That Can Form a Palindrome in a Tree?
Yes. Brute force (walk from every node) takes O(n²) time and O(n) space. Treat the tree as an undirected graph.
Which edge cases should I test for Count Paths That Can Form a Palindrome in a Tree?
A single node: there are no pairs, answer 0; A long chain (depth 10^5), which breaks naive recursion; Pairs where one node is an ancestor of the other; All edges carrying the same letter: every pair counts, n(n - 1) / 2, which needs a 64-bit result.