Count Paths That Can Form a Palindrome in a Tree

Hard Bit Manipulation XOR Basics Original on LeetCode

Reported atUber

Count Paths That Can Form a Palindrome in a Tree is a hard bit manipulation problem solved with the xor basics pattern. The best approach, optimal (root masks + hash map), runs in O(26 · n) time and O(n) space. Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (walk from every node) up.

Problem

You get a tree with n nodes numbered 0 to n - 1, rooted at node 0, described by an array parent (parent[0] == -1). For every i >= 1 there is an edge between parent[i] and i, and that edge is labelled with the letter s[i]. The character s[0] has no edge and is ignored.

Count the pairs of nodes (u, v) with u < v such that the letters on the edges of the path between u and v can be rearranged into a palindrome. An empty or one-letter sequence is a palindrome too.

Examples

Example 1

Input
parent = [-1, 0, 0, 1, 1], s = "xabab"
Output
7
Why
Edges: 0-1 'a', 0-2 'b', 1-3 'a', 1-4 'b'. Of the 10 pairs, only (1, 2), (0, 4) and (3, 4) read one 'a' and one 'b', which cannot be a palindrome.

Example 2

Input
parent = [-1, 0, 1, 2], s = "zabc"
Output
3
Why
The tree is a chain 0-1-2-3 with letters a, b, c. Only the three single-edge paths work; any longer path has two different letters.

Example 3

Input
parent = [-1, 0, 0, 0], s = "qmmm"
Output
6
Why
Every edge is 'm', so every path reads "m" or "mm". All 6 pairs count.

Constraints

  • n == parent.length == s.length
  • 1 <= n <= 10^5
  • parent[0] == -1, and for i >= 1, 0 <= parent[i] < n; the edges form a tree rooted at 0.
  • s contains only lowercase English letters; s[0] is ignored.

Solve it here

Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.

00:00
Testcase

Run checks the testcases above (3 examples, or your own). Submit also runs 13 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.

ApproachTimeSpace
Brute force (walk from every node)O(n²)O(n)
Optimal (root masks + hash map)O(26 · n)O(n)

1Brute force (walk from every node)

TimeO(n²)Each of the n traversals visits all n nodes.
SpaceO(n)The adjacency list, the visited array and the stack are all O(n).

Treat the tree as an undirected graph. From every node u, run a traversal that carries the parity mask of the path so far. Each node v > u that is reached with a mask that has at most one bit set forms a valid pair.

  1. Build an adjacency list where each edge stores its letter.
  2. For each u, traverse from u with an explicit stack, carrying the mask of the path from u.
  3. For every visited v with v > u, add 1 if mask & (mask - 1) == 0.
class Solution {
    public long countPalindromePaths(List<Integer> parent, String s) {
        int n = parent.size();
        List<List<int[]>> adj = new ArrayList<>();
        for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
        for (int i = 1; i < n; i++) {
            int p = parent.get(i), bit = 1 << (s.charAt(i) - 'a');
            adj.get(p).add(new int[] { i, bit });
            adj.get(i).add(new int[] { p, bit });
        }
        long count = 0;
        for (int u = 0; u < n; u++) {
            boolean[] seen = new boolean[n];
            Deque<int[]> stack = new ArrayDeque<>();
            stack.push(new int[] { u, 0 });
            seen[u] = true;
            while (!stack.isEmpty()) {
                int[] cur = stack.pop();
                int v = cur[0], mask = cur[1];
                if (v > u && (mask & (mask - 1)) == 0) count++;
                for (int[] e : adj.get(v)) {
                    if (!seen[e[0]]) {
                        seen[e[0]] = true;
                        stack.push(new int[] { e[0], mask ^ e[1] });
                    }
                }
            }
        }
        return count;
    }
}

2Optimal (root masks + hash map)

TimeO(26 · n)Each node does 27 hash map lookups.
SpaceO(n)The child lists, the masks and the frequency map each hold at most n entries.

Compute mask[v], the parity of letters on the path from the root to v, with an iterative traversal. For a pair (u, v) the letters on their path have parity mask[u] ^ mask[v]. Process nodes one by one and, for each, count earlier nodes with the same mask or with one of the 26 masks that differ in a single bit, using a hash map of mask frequencies.

  1. Build child lists and compute mask[v] = mask[parent[v]] ^ (1 << (s[v] - 'a')) in BFS order from the root.
  2. Walk the nodes; for each mask m add freq[m] and freq[m ^ (1 << b)] for b in 0..25.
  3. Then increment freq[m].
class Solution {
    public long countPalindromePaths(List<Integer> parent, String s) {
        int n = parent.size();
        List<List<Integer>> children = new ArrayList<>();
        for (int i = 0; i < n; i++) children.add(new ArrayList<>());
        for (int i = 1; i < n; i++) children.get(parent.get(i)).add(i);
        int[] mask = new int[n];
        int[] queue = new int[n];
        int head = 0, tail = 0;
        queue[tail++] = 0;
        while (head < tail) {
            int u = queue[head++];
            for (int v : children.get(u)) {
                mask[v] = mask[u] ^ (1 << (s.charAt(v) - 'a'));
                queue[tail++] = v;
            }
        }
        Map<Integer, Integer> freq = new HashMap<>();
        long count = 0;
        for (int v = 0; v < n; v++) {
            int m = mask[v];
            count += freq.getOrDefault(m, 0);
            for (int b = 0; b < 26; b++) {
                count += freq.getOrDefault(m ^ (1 << b), 0);
            }
            freq.merge(m, 1, Integer::sum);
        }
        return count;
    }
}

Edge cases to test

  • A single node: there are no pairs, answer 0
  • A long chain (depth 10^5), which breaks naive recursion
  • Pairs where one node is an ancestor of the other
  • All edges carrying the same letter: every pair counts, n(n - 1) / 2, which needs a 64-bit result

Hints

Hint 1

A multiset of letters can be rearranged into a palindrome exactly when at most one letter has an odd count. Store the odd/even state of all 26 letters in one 26-bit mask.

Hint 2

Let mask[v] be the parity mask of the path from the root to v. The letters on the path u-v have parity mask[u] XOR mask[v], because the shared part above their meeting point cancels.

Hint 3

Count pairs whose masks are equal or differ in exactly one bit, using a hash map from mask to how many nodes have it.

FAQ

What is the best time complexity for Count Paths That Can Form a Palindrome in a Tree?

Optimal (root masks + hash map) runs in O(26 · n) time and O(n) extra space. Each node does 27 hash map lookups.

Which pattern does Count Paths That Can Form a Palindrome in a Tree use?

It is a bit manipulation problem that uses the xor basics pattern. Other problems with the same pattern: Swap two numbers, Hamming Distance, XOR Operation in an Array.

Is there a brute force solution for Count Paths That Can Form a Palindrome in a Tree?

Yes. Brute force (walk from every node) takes O(n²) time and O(n) space. Treat the tree as an undirected graph.

Which edge cases should I test for Count Paths That Can Form a Palindrome in a Tree?

A single node: there are no pairs, answer 0; A long chain (depth 10^5), which breaks naive recursion; Pairs where one node is an ancestor of the other; All edges carrying the same letter: every pair counts, n(n - 1) / 2, which needs a 64-bit result.