Watch 9 video solutions for Count Paths That Can Form a Palindrome in a Tree, a hard level problem involving Dynamic Programming, Bit Manipulation, Tree. This walkthrough by codingMohan has 3,570 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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:
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.length1 <= n <= 1050 <= parent[i] <= n - 1 for all i >= 1parent[0] == -1parent represents a valid tree.s consists of only lowercase English letters.Problem Overview: You are given a rooted tree where each edge contributes a character. The task is to count pairs of nodes whose path characters can be rearranged to form a palindrome. A path can form a palindrome if at most one character appears an odd number of times.
Approach 1: Brute Force Path Frequency Check (O(n² * 26) time, O(n) space)
Enumerate every pair of nodes and reconstruct the path between them. Track character frequencies along the path and verify whether the counts allow a palindrome (no more than one odd frequency). This requires computing paths repeatedly, typically using parent pointers or LCA preprocessing. While straightforward conceptually, checking all pairs makes the approach quadratic and too slow for large trees.
Approach 2: DFS with Bitmask for Palindrome Check (O(n * 26) time, O(n) space)
The optimal solution relies on parity instead of full frequency counts. Maintain a 26-bit mask while running Depth-First Search. Each bit represents whether the count of a character along the current root-to-node path is odd or even. Toggle the corresponding bit when traversing an edge. Two nodes form a valid palindrome path if the XOR of their masks has either zero bits set or exactly one bit set. Use a hash map to store how many times each mask has appeared so far. For each node, add counts of matching masks (same mask or masks differing by one bit). This turns the palindrome condition into fast bit operations using bit manipulation. Because each node checks at most 26 toggled variants, the total complexity remains linear.
Approach 3: Dynamic Programming on Tree (O(n * 26) time, O(n) space)
This approach frames the same idea as a tree DP. While traversing the tree, propagate the current parity mask from parent to child. Maintain a frequency map of masks seen on the path from the root to the current node. Each node queries the map for identical masks and masks differing by one bit to count valid pairs ending at that node. The DP interpretation emphasizes accumulating results as the traversal progresses while avoiding recomputation across subtrees.
Recommended for interviews: DFS with bitmask parity is the expected solution. The brute force approach shows you understand the palindrome condition, but the bitmask trick demonstrates strong problem-solving and knowledge of parity compression with XOR operations.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Path Frequency Check | O(n² * 26) | O(n) | Useful for understanding the palindrome condition or validating small inputs |
| DFS with Bitmask Parity | O(n * 26) ≈ O(n) | O(n) | Best general solution; uses parity masks and hash lookups for fast counting |
| Dynamic Programming on Tree | O(n * 26) | O(n) | Alternative formulation when solving tree problems using DP patterns |