Scale Engineer

Count Paths That Can Form a Palindrome in a Tree

Hard
#2503Time: O(N² * H), where N is the number of nodes and H is the height of the tree. There are O(N²) pairs. For each pair, finding the path and counting characters takes O(H) time. In the worst case (a skewed tree), H can be O(N), leading to O(N³).Space: O(N) to store the tree structure. Each path-finding operation might take up to O(H) space, where H is the height of the tree.1 company
Patterns
Dynamic ProgrammingBit ManipulationBitmask
Algorithms
Depth-First Search
Data structures
Tree
Companies
thoughtspot

Prompt

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.length
  • 1 <= n <= 105
  • 0 <= parent[i] <= n - 1 for all i >= 1
  • parent[0] == -1
  • parent represents a valid tree.
  • s consists of only lowercase English letters.

Approaches

3 approaches with complexity analysis and trade-offs.

This is a straightforward brute-force approach that directly simulates the problem statement. It iterates through all possible pairs of nodes (u, v), finds the path between them, counts the frequencies of characters along that path, and checks if these characters can form a palindrome. A string can be rearranged into a palindrome if at most one of its characters appears an odd number of times.

Algorithm

  • Build Graph: Construct an adjacency list representation of the tree from the parent array.
  • Iterate All Pairs: Use nested loops to iterate through every possible pair of nodes (u, v) such that u < v.
  • Find Path: For each pair, find the path between u and v. This can be done by finding their Lowest Common Ancestor (LCA). The path consists of nodes from u to the LCA and nodes from the LCA to v.
  • Count Character Frequencies: Traverse the path and count the occurrences of each character on the edges.
  • Check Palindrome Condition: After counting, check if at most one character has an odd frequency. If so, the path can form a palindrome.
  • Count Valid Pairs: Increment a counter for each valid pair found.
  • Return Total Count: After checking all pairs, return the total count.

Walkthrough

The core of this method is to check every single pair of nodes (u, v). For each pair, we must first determine the path connecting them. In a tree, this path is unique and goes from u up to the Lowest Common Ancestor (LCA) of u and v, and then down to v. After identifying the path, we collect all characters on the edges of this path, count their frequencies, and verify the palindrome property.

Here's a sketch of the implementation:

  1. First, we convert the parent array into a more usable adjacency list representation, where each entry also stores the character associated with the edge.
  2. We then have two nested loops, for u from 0 to n-1 and for v from u+1 to n-1.
  3. Inside the loops, for a given (u, v), we find the path. A simple way to do this without a complex LCA algorithm is to trace the parents of u up to the root, storing them in a set. Then, trace the parents of v up until we find a node that is in the set; this node is the LCA. The full path is then reconstructed.
  4. We iterate over the edges in the path, count character frequencies using an array of size 26.
  5. Finally, we check the frequency array to see how many characters have odd counts. If the number of characters with odd counts is 0 or 1, we increment our total result.
// This is a conceptual snippet and would be part of a larger class structure.// A full implementation would require building the graph and helper methods for path finding. private long countPathsThatCanFormPalindrome(int n, int[] parent, String s) {    // 1. Build adjacency list (not shown for brevity)    List<List<Pair<Integer, Character>>> adj = new ArrayList<>();    for (int i = 0; i < n; i++) adj.add(new ArrayList<>());    for (int i = 1; i < n; i++) {        adj.get(parent[i]).add(new Pair<>(i, s.charAt(i)));        adj.get(i).add(new Pair<>(parent[i], s.charAt(i)));    }     long count = 0;    for (int i = 0; i < n; i++) {        for (int j = i + 1; j < n; j++) {            // 2. Find path from i to j (e.g., using BFS/DFS)            List<Character> pathChars = findPathChars(i, j, n, adj);             // 3. Check if path can form a palindrome            if (canFormPalindrome(pathChars)) {                count++;            }        }    }    return count;} private boolean canFormPalindrome(List<Character> chars) {    int[] freq = new int[26];    for (char c : chars) {        freq[c - 'a']++;    }    int oddCounts = 0;    for (int f : freq) {        if (f % 2 != 0) {            oddCounts++;        }    }    return oddCounts <= 1;} // findPathChars would be a helper function that finds the path and returns the characters.// This is non-trivial and adds to the complexity.

Complexity

Time

O(N² * H), where N is the number of nodes and H is the height of the tree. There are O(N²) pairs. For each pair, finding the path and counting characters takes O(H) time. In the worst case (a skewed tree), H can be O(N), leading to O(N³).

Space

O(N) to store the tree structure. Each path-finding operation might take up to O(H) space, where H is the height of the tree.

Trade-offs

Pros

  • Simple to understand and implement.

  • Directly follows the problem description.

Cons

  • Extremely inefficient due to nested loops and repeated path traversals.

  • Finding the path and LCA for every pair is computationally expensive.

  • Will result in a 'Time Limit Exceeded' error on large inputs.

Solutions

class Solution {private  List<int[]>[] g;private  Map<Integer, Integer> cnt = new HashMap<>();private  long ans;public  long countPalindromePaths(List<Integer> parent, String s) {    int n = parent.size();    g = new List[n];    cnt.put(0, 1);    Arrays.setAll(g, k->new ArrayList<>());    for (int i = 1; i < n; ++i) {      int p = parent.get(i);      g[p].add(new int[]{i, 1 << (s.charAt(i) - 'a')});    }    dfs(0, 0);    return ans;  }private  void dfs(int i, int xor) {    for (int[] e : g[i]) {      int j = e[0], v = e[1];      int x = xor^v;      ans += cnt.getOrDefault(x, 0);      for (int k = 0; k < 26; ++k) {        ans += cnt.getOrDefault(x ^ (1 << k), 0);      }      cnt.merge(x, 1, Integer : : sum);      dfs(j, x);    }  }}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem