Class Solution
java.lang.Object
g2701_2800.s2791_count_paths_that_can_form_a_palindrome_in_a_tree.Solution
2791 - Count Paths That Can Form a Palindrome in a Tree.<p>Hard</p>
<p>You are given a <strong>tree</strong> (i.e. a connected, undirected graph that has no cycles) <strong>rooted</strong> at node <code>0</code> consisting of <code>n</code> nodes numbered from <code>0</code> to <code>n - 1</code>. The tree is represented by a <strong>0-indexed</strong> array <code>parent</code> of size <code>n</code>, where <code>parent[i]</code> is the parent of node <code>i</code>. Since node <code>0</code> is the root, <code>parent[0] == -1</code>.</p>
<p>You are also given a string <code>s</code> of length <code>n</code>, where <code>s[i]</code> is the character assigned to the edge between <code>i</code> and <code>parent[i]</code>. <code>s[0]</code> can be ignored.</p>
<p>Return <em>the number of pairs of nodes</em> <code>(u, v)</code> <em>such that</em> <code>u < v</code> <em>and the characters assigned to edges on the path from</em> <code>u</code> <em>to</em> <code>v</code> <em>can be <strong>rearranged</strong> to form a <strong>palindrome</strong></em>.</p>
<p>A string is a <strong>palindrome</strong> when it reads the same backwards as forwards.</p>
<p><strong>Example 1:</strong></p>
<p><img src="https://assets.leetcode.com/uploads/2023/07/15/treedrawio-8drawio.png" alt="" /></p>
<p><strong>Input:</strong> parent = [-1,0,0,1,1,2], s = “acaabc”</p>
<p><strong>Output:</strong> 8</p>
<p><strong>Explanation:</strong></p>
<p>The valid pairs are:</p>
<ul>
<li>
<p>All the pairs (0,1), (0,2), (1,3), (1,4) and (2,5) result in one character which is always a palindrome.</p>
</li>
<li>
<p>The pair (2,3) result in the string “aca” which is a palindrome.</p>
</li>
<li>
<p>The pair (1,5) result in the string “cac” which is a palindrome.</p>
</li>
<li>
<p>The pair (3,5) result in the string “acac” which can be rearranged into the palindrome “acca”.</p>
</li>
</ul>
<p><strong>Example 2:</strong></p>
<p><strong>Input:</strong> parent = [-1,0,0,0,0], s = “aaaaa”</p>
<p><strong>Output:</strong> 10</p>
<p><strong>Explanation:</strong> Any pair of nodes (u,v) where u < v is valid.</p>
<p><strong>Constraints:</strong></p>
<ul>
<li><code>n == parent.length == s.length</code></li>
<li><code>1 <= n <= 10<sup>5</sup></code></li>
<li><code>0 <= parent[i] <= n - 1</code> for all <code>i >= 1</code></li>
<li><code>parent[0] == -1</code></li>
<li><code>parent</code> represents a valid tree.</li>
<li><code>s</code> consists of only lowercase English letters.</li>
</ul>
-
Constructor Summary
Constructors -
Method Summary
-
Constructor Details
-
Solution
public Solution()
-
-
Method Details
-
countPalindromePaths
-