# Count Paths That Can Form a Palindrome in a Tree **Difficulty:** HARD [External](https://leetcode.com/problems/count-paths-that-can-form-a-palindrome-in-a-tree) Canonical: https://scaleengineer.com/dsa/problems/count-paths-that-can-form-a-palindrome-in-a-tree **Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming), [Bit Manipulation](https://scaleengineer.com/dsa/patterns/bit-manipulation), [Bitmask](https://scaleengineer.com/dsa/patterns/bitmask) **Algorithms:** [Depth-First Search](https://scaleengineer.com/algorithms/depth-first-search) **Data structures:** Tree **Companies:** [thoughtspot](https://scaleengineer.com/companies/thoughtspot) --- ## Problem You are given a **tree** (i.e. 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 be **rearranged** to form a **palindrome**_. A string is a **palindrome** when it reads the same backwards as forwards. **Example 1:** ![](https://assets.glich.co/dsa/count-paths-that-can-form-a-palindrome-in-a-tree/image0.png) **Input:** parent = [-1,0,0,1,1,2], s = "acaabc" **Output:** 8 **Explanation:** The valid pairs are: - All the pairs (0,1), (0,2), (1,3), (1,4) and (2,5) result in one character which is always a palindrome. - The pair (2,3) result in the string "aca" which is a palindrome. - The pair (1,5) result in the string "cac" which is a palindrome. - The pair (3,5) result in the string "acac" which can be rearranged into the palindrome "acca". **Example 2:** **Input:** parent = [-1,0,0,0,0], s = "aaaaa" **Output:** 10 **Explanation:** Any pair of nodes (u,v) where u < v is valid. **Constraints:** * `n == parent.length == s.length` * `1 <= n <= 105` * `0 <= parent[i] <= n - 1` for all `i >= 1` * `parent[0] == -1` * `parent` represents a valid tree. * `s` consists of only lowercase English letters. # Approaches ## Brute-Force by Iterating All Pairs This is a straightforward brute-force approach that directly simulates the problem statement. It iterates through all possible pairs of nodes `(u, v)`, finds the path between them, counts the frequencies of characters along that path, and checks if these characters can form a palindrome. A string can be rearranged into a palindrome if at most one of its characters appears an odd number of times. **Time:** O(N² * H), where N is the number of nodes and H is the height of the tree. There are O(N²) pairs. For each pair, finding the path and counting characters takes O(H) time. In the worst case (a skewed tree), H can be O(N), leading to O(N³). · **Space:** O(N) to store the tree structure. Each path-finding operation might take up to O(H) space, where H is the height of the tree. **Pros:** Simple to understand and implement.; Directly follows the problem description. **Cons:** Extremely inefficient due to nested loops and repeated path traversals.; Finding the path and LCA for every pair is computationally expensive.; Will result in a 'Time Limit Exceeded' error on large inputs. ### Explanation The core of this method is to check every single pair of nodes `(u, v)`. For each pair, we must first determine the path connecting them. In a tree, this path is unique and goes from `u` up to the Lowest Common Ancestor (LCA) of `u` and `v`, and then down to `v`. After identifying the path, we collect all characters on the edges of this path, count their frequencies, and verify the palindrome property. Here's a sketch of the implementation: 1. First, we convert the `parent` array into a more usable adjacency list representation, where each entry also stores the character associated with the edge. 2. We then have two nested loops, `for u from 0 to n-1` and `for v from u+1 to n-1`. 3. Inside the loops, for a given `(u, v)`, we find the path. A simple way to do this without a complex LCA algorithm is to trace the parents of `u` up to the root, storing them in a set. Then, trace the parents of `v` up until we find a node that is in the set; this node is the LCA. The full path is then reconstructed. 4. We iterate over the edges in the path, count character frequencies using an array of size 26. 5. Finally, we check the frequency array to see how many characters have odd counts. If the number of characters with odd counts is 0 or 1, we increment our total result. ```java // This is a conceptual snippet and would be part of a larger class structure. // A full implementation would require building the graph and helper methods for path finding. private long countPathsThatCanFormPalindrome(int n, int[] parent, String s) { // 1. Build adjacency list (not shown for brevity) List>> adj = new ArrayList<>(); for (int i = 0; i < n; i++) adj.add(new ArrayList<>()); for (int i = 1; i < n; i++) { adj.get(parent[i]).add(new Pair<>(i, s.charAt(i))); adj.get(i).add(new Pair<>(parent[i], s.charAt(i))); } long count = 0; for (int i = 0; i < n; i++) { for (int j = i + 1; j < n; j++) { // 2. Find path from i to j (e.g., using BFS/DFS) List pathChars = findPathChars(i, j, n, adj); // 3. Check if path can form a palindrome if (canFormPalindrome(pathChars)) { count++; } } } return count; } private boolean canFormPalindrome(List chars) { int[] freq = new int[26]; for (char c : chars) { freq[c - 'a']++; } int oddCounts = 0; for (int f : freq) { if (f % 2 != 0) { oddCounts++; } } return oddCounts <= 1; } // findPathChars would be a helper function that finds the path and returns the characters. // This is non-trivial and adds to the complexity. ``` ### Algorithm - **Build Graph:** Construct an adjacency list representation of the tree from the `parent` array. - **Iterate All Pairs:** Use nested loops to iterate through every possible pair of nodes `(u, v)` such that `u < v`. - **Find Path:** For each pair, find the path between `u` and `v`. This can be done by finding their Lowest Common Ancestor (LCA). The path consists of nodes from `u` to the LCA and nodes from the LCA to `v`. - **Count Character Frequencies:** Traverse the path and count the occurrences of each character on the edges. - **Check Palindrome Condition:** After counting, check if at most one character has an odd frequency. If so, the path can form a palindrome. - **Count Valid Pairs:** Increment a counter for each valid pair found. - **Return Total Count:** After checking all pairs, return the total count. ## Brute-Force with Precomputed Path Masks This approach improves upon the first one by using a clever bitmasking trick. Instead of recounting character frequencies for each path, we precompute a 'path mask' for every node. This mask represents the parity of character counts on the path from the root to that node. The mask for the path between any two nodes `u` and `v` can then be found in O(1) by XORing their individual root-to-node path masks. This avoids the expensive path-finding step inside the main loop, reducing the complexity for each pair check from O(H) to O(1). **Time:** O(N²). Precomputing all path masks takes O(N). The nested loops to check all pairs take O(N²), with each check being O(1). · **Space:** O(N) for the adjacency list, the queue for BFS, and the `masks` array. **Pros:** Much faster than the first approach.; Introduces the key insight of using bitmasks for path properties. **Cons:** The O(N²) complexity is still too slow for the given constraints (N up to 10^5).; Will result in a 'Time Limit Exceeded' error on large test cases. ### Explanation The key idea is to represent character counts as bitmasks. Since we only care about whether a character count is odd or even, a 26-bit integer suffices. The `k`-th bit is set if the character `'a' + k` appears an odd number of times on a path. The mask for the path from `u` to `v` can be calculated as `mask_from_root(u) ^ mask_from_root(v)`. This works because edges on the common path from the root to `lca(u,v)` are included in both masks, and the XOR operation cancels them out, leaving only the edges on the unique parts of the paths from the root to `u` and `v`. The algorithm is as follows: 1. Build the adjacency list for the tree. 2. Perform a single DFS or BFS traversal starting from the root (node 0) to compute the path mask for every node. Let's say `masks[i]` stores the mask for the path from the root to node `i`. `masks[0]` is 0. For any other node `i` with parent `p`, `masks[i] = masks[p] ^ (1 << (s[i] - 'a'))`. 3. After precomputation, iterate through all pairs `(u, v)` with `u < v`. 4. For each pair, calculate `pathMask = masks[u] ^ masks[v]`. 5. A path can form a palindrome if its mask is zero (all even counts) or a power of two (one odd count). We check this condition: `pathMask == 0 || (pathMask > 0 && (pathMask & (pathMask - 1)) == 0)`. 6. If the condition is met, we increment our result counter. ```java class Solution { public long countPalindromePaths(List parent, String s) { int n = parent.size(); List>> adj = new ArrayList<>(); for (int i = 0; i < n; i++) adj.add(new ArrayList<>()); for (int i = 1; i < n; i++) { adj.get(parent.get(i)).add(new Pair<>(i, 1 << (s.charAt(i) - 'a'))); } int[] masks = new int[n]; // Precompute masks from root to each node Queue q = new LinkedList<>(); q.offer(0); masks[0] = 0; while (!q.isEmpty()) { int u = q.poll(); for (Pair edge : adj.get(u)) { int v = edge.getKey(); int charMask = edge.getValue(); masks[v] = masks[u] ^ charMask; q.offer(v); } } long count = 0; for (int i = 0; i < n; i++) { for (int j = i + 1; j < n; j++) { int pathMask = masks[i] ^ masks[j]; if ((pathMask & (pathMask - 1)) == 0) { count++; } } } return count; } } // Note: In LeetCode, parent is a List, not an array. // Pair class would be a simple helper class or use an array int[2]. ``` ### Algorithm - **Bitmask Insight:** Realize that a path can form a palindrome if the bitmask of its character parities has at most one bit set. The `i`-th bit is 1 if the `i`-th letter appears an odd number of times, 0 otherwise. - **Path Mask Calculation:** The mask for a path between `u` and `v` is `mask(u) ^ mask(v)`, where `mask(x)` is the mask for the path from the root to node `x`. - **Precompute Masks:** Perform a single tree traversal (DFS or BFS) from the root to compute `mask(i)` for every node `i`. - **Iterate All Pairs:** Use nested loops to iterate through all pairs `(u, v)` with `u < v`. - **Check Condition:** For each pair, calculate the path mask `p = mask(u) ^ mask(v)`. Check if `p` is 0 or a power of two. A number `p > 0` is a power of two if `(p & (p - 1)) == 0`. - **Count and Return:** Increment a counter for each valid pair and return the total. ## Optimal Approach using Path Mask Frequencies This optimal approach completely avoids the O(N²) pair iteration. It leverages the path mask insight and focuses on counting. After computing all root-to-node path masks in a single O(N) traversal, we count how many times each mask appears. The problem then transforms into a combinatorial one: given the counts of different masks, how many pairs `(u, v)` satisfy the condition `mask(u) ^ mask(v) = 0` or `mask(u) ^ mask(v) = 2^k`? This can be solved efficiently by iterating through the unique masks and their frequencies. **Time:** O(N). Building the graph takes O(N). The DFS to compute masks and populate the frequency map takes O(N). The final counting step iterates through unique masks (at most N) and for each, checks 26 other masks. This gives a complexity of O(N + M * 26), where M is the number of unique masks (M <= N), which simplifies to O(N). · **Space:** O(N) to store the adjacency list, recursion stack for DFS, and the frequency map. The number of unique masks in the map is at most N. **Pros:** Highly efficient with linear time complexity.; Solves the problem within the time limits for large inputs.; Elegant solution combining graph traversal, bit manipulation, and combinatorics. **Cons:** The logic for counting from frequencies can be slightly tricky to get right, especially avoiding double counting. ### Explanation This method is the most efficient and is necessary to pass the given constraints. It builds upon the path mask idea from Approach 2 but uses a more advanced counting technique. **Algorithm Steps:** 1. **Build Adjacency List:** As before, create an adjacency list from the `parent` array to represent the tree. Store the character's bitmask value with each edge. 2. **Compute All Path Masks:** Traverse the tree using DFS (or BFS) from the root. During the traversal, compute the path mask for each node, which is the XOR sum of edge character masks from the root to the current node. Store these masks in an array or list. 3. **Count Frequencies:** Create a `HashMap` to store the frequency of each path mask. Iterate through the computed masks and populate this map. 4. **Calculate Total Pairs:** - Initialize a `long` variable `ans = 0`. - Iterate over each entry (`mask`, `count`) in the frequency map. - **Paths with mask 0:** These correspond to pairs of nodes `(u, v)` that have the same root-to-node path mask (`mask(u) == mask(v)`). For a given mask that appears `count` times, we can form `count * (count - 1) / 2` such pairs. Add this to `ans`. - **Paths with one bit set:** These correspond to pairs `(u, v)` where `mask(u)` and `mask(v)` differ by exactly one bit. For each `mask` from our frequency map, we check 26 possibilities. For each bit `j` from 0 to 25, we form a `targetMask = mask ^ (1 << j)`. If this `targetMask` exists in our frequency map, we can form `count * freqMap.get(targetMask)` new valid pairs. To avoid counting each pair twice (once for `mask` and once for `targetMask`), we only add pairs when `mask < targetMask`. This counting method ensures that every valid pair is counted exactly once. ```java import java.util.ArrayList; import java.util.HashMap; import java.util.List; import java.util.Map; class Solution { public long countPalindromePaths(List parent, String s) { int n = parent.size(); List> adj = new ArrayList<>(); for (int i = 0; i < n; i++) { adj.add(new ArrayList<>()); } for (int i = 1; i < n; i++) { adj.get(parent.get(i)).add(new int[]{i, s.charAt(i) - 'a'}); } Map freq = new HashMap<>(); dfs(0, 0, adj, freq); long ans = 0; for (Map.Entry entry : freq.entrySet()) { int mask = entry.getKey(); long count = entry.getValue(); // Case 1: Paths with mask 0 (u and v have same path mask from root) ans += count * (count - 1) / 2; // Case 2: Paths with one bit set (u and v masks differ by one bit) for (int i = 0; i < 26; i++) { int targetMask = mask ^ (1 << i); if (mask < targetMask && freq.containsKey(targetMask)) { ans += count * freq.get(targetMask); } } } return ans; } private void dfs(int u, int currentMask, List> adj, Map freq) { freq.put(currentMask, freq.getOrDefault(currentMask, 0) + 1); for (int[] edge : adj.get(u)) { int v = edge[0]; int charIndex = edge[1]; dfs(v, currentMask ^ (1 << charIndex), adj, freq); } } } ``` ### Algorithm - **Path Masks:** Use the same bitmask representation as in the previous approach. The goal is to count pairs `(u, v)` where `mask(u) ^ mask(v)` is 0 or a power of 2. - **Compute All Masks:** Traverse the tree once with DFS or BFS to compute the root-to-node path mask for every node. - **Count Mask Frequencies:** Store the frequency of each unique path mask in a HashMap, e.g., `freqMap[mask] = count`. - **Calculate Pairs from Frequencies:** - Initialize `totalPairs = 0`. - Iterate through each `mask` and its `count` in the `freqMap`. - **Case 1 (Zero difference):** For paths where `mask(u) == mask(v)`, the path mask is 0. The number of such pairs for a given mask is `count * (count - 1) / 2`. Add this to `totalPairs`. - **Case 2 (One bit difference):** For paths where `mask(u) ^ mask(v)` is a power of two, iterate through each bit `k` from 0 to 25. Let `targetMask = mask ^ (1 << k)`. If `freqMap` contains `targetMask`, we can form `count * freqMap.get(targetMask)` pairs. To avoid double-counting (e.g., counting `(m, m')` and later `(m', m)`), we only process pairs where `mask < targetMask`. - **Return Result:** The final `totalPairs` is the answer. # Solutions ### Java ```java class Solution { private List[] g; private Map cnt = new HashMap<>(); private long ans; public long countPalindromePaths(List parent, String s) { int n = parent.size(); g = new List[n]; cnt.put(0, 1); Arrays.setAll(g, k->new ArrayList<>()); for (int i = 1; i < n; ++i) { int p = parent.get(i); g[p].add(new int[]{i, 1 << (s.charAt(i) - 'a')}); } dfs(0, 0); return ans; } private void dfs(int i, int xor) { for (int[] e : g[i]) { int j = e[0], v = e[1]; int x = xor^v; ans += cnt.getOrDefault(x, 0); for (int k = 0; k < 26; ++k) { ans += cnt.getOrDefault(x ^ (1 << k), 0); } cnt.merge(x, 1, Integer : : sum); dfs(j, x); } } } ``` ### CPP ```cpp class Solution { public: long long countPalindromePaths(vector &parent, string s) { int n = parent.size(); vector>> g(n); unordered_map cnt; cnt[0] = 1; for (int i = 1; i < n; ++i) { int p = parent[i]; g[p].emplace_back(i, 1 << (s[i] - 'a')); } long long ans = 0; function dfs = [&](int i, int xo) { for (auto [j, v] : g[i]) { int x = xo ^ v; ans += cnt[x]; for (int k = 0; k < 26; ++k) { ans += cnt[x ^ (1 << k)]; } ++cnt[x]; dfs(j, x); } }; dfs(0, 0); return ans; } }; ``` ### Python ```python class Solution: def countPalindromePaths(self, parent: List[int], s: str) -> int: def dfs(i: int, xor: int): nonlocal ans for j, v in g[i]: x = xor ^ v ans += cnt[x] for k in range(26): ans += cnt[x ^ (1 << k)] cnt[x] += 1 dfs(j, x) n = len(parent) g = defaultdict(list) for i in range(1, n): p = parent[i] g[p]. append((i, 1 << (ord(s[i]) - ord('a')))) ans = 0 cnt = Counter({0: 1}) dfs(0, 0) return ans ```