We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Count Paths That Can Form a Palindrome in a Tree

Number: 2905

Difficulty: Hard

Paid? No

Companies: thoughtspot, TikTok

Problem Description

Given a rooted tree represented by a parent array and a string s in which s[i] characterizes the edge between node i and its parent (ignoring s[0] for the root), count the number of pairs of nodes (u, v) with u < v such that the collection of characters on the path from u to v can be rearranged to form a palindrome.

Key Insights

  • The key palindrome condition is that at most one character can have an odd frequency.
  • Represent the frequencies using a bitmask (26 bits for lower-case English letters); toggling a bit changes a character's parity.
  • For a given node, compute its bitmask from root to the node by DFS.
  • The XOR of two nodes’ bitmasks gives the parity counts along the path between them.
  • A valid path’s bitmask must have at most one bit set (0 or one bit toggled).
  • Use a hash map (or dictionary) to count the frequencies of masks encountered during DFS.
  • Count valid pairs by directly checking the current mask in the dictionary and then all masks that differ by exactly one bit.

Space and Time Complexity

Time Complexity: O(n * 26) which is effectively O(n) since 26 is constant.
Space Complexity: O(n), due to the recursion stack and hash map used to store intermediate bitmask frequencies.

Solution

We perform a DFS starting from the root and maintain a cumulative bitmask for each node where each bit represents the parity (even/odd) frequency of each character on the path from the root. For each visiting node, we:

  1. Check the frequency map for the same bitmask (which means the path from a previously visited node to this node has a perfect palindrome condition).
  2. Check for masks that differ by one bit (allowing one odd frequency).
  3. Add the current bitmask to the frequency map, traverse children, and then remove it (backtracking).

Code Solutions

Below are the code solutions in Python, JavaScript, C++, and Java.

# Python solution using DFS and a dictionary to count the frequency of bit masks.
def countPalindromicPaths(parent, s):
    from collections import defaultdict
    n = len(parent)
    # Build the tree as an adjacency list
    tree = [[] for _ in range(n)]
    for child in range(1, n):
        tree[parent[child]].append(child)
    
    freq = defaultdict(int)
    freq[0] = 1  # initial mask for root
    result = 0
    
    # DFS helper that tracks the current bitmask
    def dfs(node, mask):
        nonlocal result
        # Count valid pairs using the current mask:
        result += freq[mask]
        for i in range(26):
            toggled_mask = mask ^ (1 << i)
            result += freq[toggled_mask]
        
        # Include current mask in our frequency map
        freq[mask] += 1
        
        # Explore children and update the mask based on the corresponding edge character
        for child in tree[node]:
            new_mask = mask ^ (1 << (ord(s[child]) - ord('a')))
            dfs(child, new_mask)
        
        # Backtrack: remove current mask before returning
        freq[mask] -= 1
    
    dfs(0, 0)
    return result

# Example usage:
parent = [-1, 0, 0, 1, 1, 2]
s = "acaabc"
print(countPalindromicPaths(parent, s))
← Back to All Questions