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.
We can use a Depth First Search (DFS) approach combined with a bitmask to efficiently determine if the characters along a path can be rearranged into a palindrome. The idea is as follows:
This Python solution uses DFS to navigate through the tree starting from the root node. We maintain a bitmask `path` that helps track character parity. For any given node to node path within the tree, the XOR of their paths determines if the characters can form a palindrome. The usage of memoization via the `memo` dictionary helps in efficiently checking these conditions for all node pairs.
Time Complexity: O(n), where n is the number of nodes because each node and each edge in the tree is visited once.
Space Complexity: O(n), for storing the tree structure and the memoization dictionary.
Another approach to solve this problem is using dynamic programming on trees. The idea is to precompute some information at each node that helps in determining the palindromic nature of any two nodes quickly.
The Java solution uses dynamic programming to calculate character frequency masks for each node. This mask is then used to determine palindromic potential between any two nodes. While dynamic programming is used, the main palindromic check still hinges on bit manipulation to quickly assess parity conditions between nodes.
Time Complexity: Although we precompute data, combining this with the mask checking gives an overall complexity similar to O(n^2).
Space Complexity: O(n), for storing precomputed masks and the map of frequency masks.
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| DFS with Bitmask for Palindrome Check | Time Complexity: O(n), where n is the number of nodes because each node and each edge in the tree is visited once. |
| Dynamic Programming on Tree | Time Complexity: Although we precompute data, combining this with the mask checking gives an overall complexity similar to O(n^2). |
| Default Approach | — |
| 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 |
2791. Count Paths That Can Form a Palindrome in a Tree | O(N^3) - O(N*N) - O(N) |Leetcode Weekly 355 • codingMohan • 3,570 views views
Watch 8 more video solutions →Practice Count Paths That Can Form a Palindrome in a Tree with our built-in code editor and test cases.
Practice on FleetCode