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

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Count Paths That Can Form a Palindrome in a Tree

Difficulty: Hard

Problem Description

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.

Key Insights

  • A string can be rearranged to form a palindrome if at most one character has an odd count.
  • The path between two nodes in a tree can be represented by their lowest common ancestor (LCA).
  • To efficiently count pairs, we can use a bitmask to track the parity of character counts along each path.
  • Depth-First Search (DFS) can be utilized to traverse the tree and compute paths.

Space and Time Complexity

Time Complexity: O(n)
Space Complexity: O(n)

Solution

The problem can be solved using a Depth-First Search (DFS) approach combined with bit manipulation. We will maintain a bitmask representing the count of characters on the path from the root to the current node. During the DFS traversal, we will explore all possible pairs of nodes, using the bitmask to check how many characters have odd counts. If the number of characters with odd counts is less than or equal to one, the path can form a palindrome.

Code Solutions

def countPalindromePaths(parent, s):
    from collections import defaultdict
    
    n = len(parent)
    tree = defaultdict(list)
    
    # Build the tree from the parent array
    for i in range(1, n):
        tree[parent[i]].append(i)

    def dfs(node, bitmask):
        nonlocal count
        # Toggle the bit for the current character
        bitmask ^= (1 << (ord(s[node]) - ord('a')))
        
        # Count the current bitmask
        count += mask_count[bitmask]  # Count paths with the same bitmask
        for i in range(26):
            count += mask_count[bitmask ^ (1 << i)]  # Count paths with one odd character
        
        mask_count[bitmask] += 1
        
        for child in tree[node]:
            dfs(child, bitmask)
        
        mask_count[bitmask] -= 1  # Backtrack

    count = 0
    mask_count = defaultdict(int)
    mask_count[0] = 1  # Count the empty path
    
    dfs(0, 0)
    
    return count
← Back to All Questions