#2791

Hard

auto_awesomeBinary-tree traversal and state tracking

LeetCode Problem Workspace

Count Paths That Can Form a Palindrome in a Tree

This problem asks you to count all node pairs in a tree whose path characters can be rearranged into a palindrome using bitmask tracking.

dynamic programming bit manipulation tree depth first search bitmask

Problem Statement

Given a rooted tree with n nodes numbered from 0 to n - 1, represented by a 0-indexed array parent where parent[0] == -1 and parent[i] is the parent of node i, determine how many pairs of nodes have paths whose characters can form a palindrome. Each edge from parent[i] to i is labeled with a character s[i], with s[0] ignored since node 0 has no parent.

Return the number of node pairs (u, v) with u < v such that the sequence of characters along the path from u to v can be rearranged to form a palindrome. For example, the path 'aca' is already a palindrome and 'acac' can be rearranged into 'acca'.

Examples

Example 1

Input: parent = [-1,0,0,1,1,2], s = "acaabc"

Output: 8

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

Any pair of nodes (u,v) where u < v is valid.

Constraints

n == parent.length == s.length
1 <= n <= 105
0 = 1
parent[0] == -1
parent represents a valid tree.
s consists of only lowercase English letters.

Solution Approach

Use Bitmasking to Track Character Parity

Represent each character along a path as a bit in an integer, flipping the corresponding bit when passing a node. A path can form a palindrome if the bitmask has at most one bit set, representing at most one character with odd frequency.

Depth-First Search with Memoization

Traverse the tree using DFS while carrying the current bitmask. Store the count of each bitmask in a hashmap. When visiting a node, check current and single-bit-flipped bitmasks in the hashmap to count valid palindrome-forming paths efficiently.

Count Node Pairs Efficiently

For each node, compute the number of valid paths ending at this node using the hashmap. Accumulate counts recursively, ensuring pairs are only counted once with u < v. This avoids the O(n^2) brute-force pair checking.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(n) because each node is visited once and bitmask operations are constant time. Space complexity is O(n) for storing the hashmap of bitmask counts and recursion stack.

What Interviewers Usually Probe

Look for solutions that efficiently track character counts along tree paths.
Consider using bit manipulation to represent character parity instead of arrays.
Be prepared to explain how DFS and hashmap counting reduce redundant pair checks.

Common Pitfalls or Variants

Common pitfalls

Counting all pairs without using bitmask can lead to O(n^2) time and timeouts.
Incorrectly flipping bits for character counts can miscount palindromic paths.
Not handling single-bit differences when checking for palindrome possibilities.

Follow-up variants

Count paths forming palindromes in a tree where each edge has a numeric label instead of a character.
Return all paths themselves that can form palindromes instead of just counting.
Allow paths to start or end at any node, not just pairs with u < v.

FAQ

What is the core idea behind Count Paths That Can Form a Palindrome in a Tree?

Use DFS with bitmasking to track character parity along tree paths; a path is palindromic if at most one bit is set in the mask.

Why do we flip bits instead of counting characters directly?

Flipping bits represents the parity of each character efficiently and lets us check palindrome conditions in constant time.

Can this approach handle large trees up to 10^5 nodes?

Yes, because DFS with bitmasking and hashmap counting ensures O(n) time and space usage.

How do we avoid counting the same node pair twice?

By only considering pairs with u < v and accumulating counts during DFS, each pair is counted once.

What patterns from this problem appear in other tree palindrome questions?

The combination of tree traversal, state tracking, and bitmask parity checking is common for palindrome path problems in trees.

terminal

Solution

Solution 1

#### Python3

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

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

Continue Practicing

#3575 maximum good subtree score #2920 maximum points after collecting coins from all nodes #3376 minimum time to break locks i