Show problems as
Classic problem #2791HardHash TableBit ManipulationTreeDepth-First Search

Count Paths That Can Form a Palindrome in a Tree

Real-world version: Stencilled Routes That Rearrange To A Palindrome
Tracked in this browser only
Read Count Paths That Can Form a Palindrome in a Tree on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

A parcel carrier runs n stations labelled 0 through n - 1, with station 0 acting as the depot. For every station i other than the depot, parent[i] is the one station that sits one hop closer to the depot, and parent[0] is -1. These hops form a single tree, so exactly one route without repeats joins any two stations.

The hop between station i and parent[i] carries a stencil, and that stencil is the lowercase letter s[i]. The depot has no hop above it, so the letter s[0] is a filler that no route ever reads.

Reading the stencils along a route in the order it crosses them gives that route's label. Call a label foldable when its letters can be reordered so the result matches itself read backwards.

Return how many pairs of stations (u, v) with u < v have a foldable route label. The tally can exceed the range of a 32-bit integer.

Examples

Example 1

Input
parent = [-1,0,0,1,1], s = "zaabb"
Output
8

The eight qualifying pairs are (0,1), (0,2), (1,2), (1,3), (1,4), (2,3), (2,4) and (3,4). The route from 2 to 3 has label `aab`, which reorders to `aba`. The routes 0 to 3 and 0 to 4 both have label `ab`, and no reordering of `ab` matches itself backwards. The pair (0,1) uses only the hop stencilled `a`, and a one-letter label always qualifies.

Example 2

Input
parent = [-1,0,1,2], s = "wxyz"
Output
3

The stations sit in a line 0 - 1 - 2 - 3 with stencils `x`, `y`, `z`. Only the three single-hop pairs (0,1), (1,2) and (2,3) qualify; every longer route here has a label of distinct letters, such as `xy` or `xyz`.

Example 3

Input
parent = [-1], s = "k"
Output
0

There is only the depot, so no pair `(u, v)` with `u < v` exists and the filler letter `k` is never read.

Example 4

Input
parent = [-1,0,0,0], s = "cmmm"
Output
6

Three stations hang directly off the depot and every hop is stencilled `m`. All six pairs qualify: the three depot pairs have label `m`, and the three pairs among stations 1, 2 and 3 have label `mm`.

Constraints

  • n == parent.length == s.length
  • 1 <= n <= 10^5
  • parent[0] == -1
  • 0 <= parent[i] <= n - 1 for every i >= 1
  • parent describes one valid tree rooted at station 0.
  • s consists of lowercase English letters only.

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def count_palindrome_paths(parent: list[int], s: str) -> int:
Java
public long countPalindromePaths(List<Integer> parent, String s)

More on the same topics