Count Tree Paths Whose Edge Letters Can Form a Palindrome
Company: Goldman Sachs
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: hard
Interview Round: Other
# Count Tree Paths Whose Edge Letters Can Form a Palindrome
You are given a connected, undirected tree with no cycles, rooted at node `0`. Its `n` nodes are numbered from `0` through `n - 1`. A 0-indexed array `parent` gives each node's parent, with `parent[0] == -1`.
String `s` has length `n`. For every nonroot node `i`, `s[i]` labels the edge between `i` and `parent[i]`; `s[0]` is ignored.
Return the number of node pairs `(u, v)` with `u < v` for which the letters on their unique connecting path can be rearranged into a palindrome. A palindrome reads the same forward and backward. The letters need not already appear in palindromic order along the path.
### Examples
**Example 1**
```text
Input: parent = [-1,0,0,1], s = "zaab"
Output: 5
```
The edges `0-1`, `0-2`, and `1-3` have labels `a`, `a`, and `b`. Their three endpoint pairs qualify. Pair `(1,2)` gives `aa`, and pair `(2,3)` gives `aab`, which can be rearranged as `aba`. Pair `(0,3)` gives `ab` and does not qualify. The root's `z` is not an edge label.
**Example 2**
```text
Input: parent = [-1,2,0], s = "qab"
Output: 2
```
Node `2` is the parent of node `1`. The edges `0-2` and `2-1` have labels `b` and `a`, so pairs `(0,2)` and `(1,2)` qualify. The path for `(0,1)` has both letters and cannot be rearranged into a palindrome.
### Constraints
- `n == parent.length == s.length`.
- `1 <= n <= 10^5`.
- `0 <= parent[i] <= n - 1` for all `i >= 1`.
- `parent[0] == -1`.
- `parent` represents a valid tree.
- `s` contains only lowercase English letters.
### Clarifying Questions
- Are letters stored on nodes? No; `s[i]` labels the edge from nonroot node `i` to its parent.
- Are paths restricted to ancestor-descendant pairs? No; count paths between any two distinct nodes.
- Must the existing letter sequence be a palindrome? No; rearrangement is allowed.
- Can a node pair with itself be counted? No; `u < v` excludes it and counts each distinct unordered pair once.
- Is a parent always numbered before its child? No such ordering is promised; only a valid rooted tree is guaranteed.
### C++ Interface
```cpp
class Solution {
public:
long long countPalindromePaths(vector<int>& parent, string s) {
}
};
```
### Reasoning Checkpoints
- Distinguish the ignored root character from real edge labels.
- Support paths that pass through a common ancestor without assuming node-number order.
- Count qualifying pairs once while avoiding enumeration of all paths.
```hint Rearranging the path letters
What restrictions on odd and even character counts allow a multiset of letters to be arranged symmetrically around a center?
```
Overview: Count distinct node pairs whose connecting tree path has edge letters that can be rearranged into a palindrome, with the root character ignored.