2791. Count Paths That Can Form a Palindrome in a Tree LeetCode Solution
In this guide, you will get 2791. Count Paths That Can Form a Palindrome in a Tree LeetCode Solution with the best time and space complexity. The solution to Count Paths That Can Form a Palindrome in a Tree problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Problem Statement of Count Paths That Can Form a Palindrome in a Tree
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”.
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] = 1
parent[0] == -1
parent represents a valid tree.
s consists of only lowercase English letters.
Complexity Analysis
Time Complexity:
Space Complexity:
2791. Count Paths That Can Form a Palindrome in a Tree LeetCode Solution in C++
class Solution {
public:
long long countPalindromePaths(vector<int>& parent, string s) {
// A valid (u, v) has at most 1 letter with odd frequency on its path. The
// frequency of a letter on the u-v path is equal to the sum of its
// frequencies on the root-u and root-v paths substract twice of its
// frequency on the root-LCA(u, v) path. Considering only the parity
// (even/odd), the part involving root-LCA(u, v) can be ignored, making it
// possible to calculate both parts easily using a simple DFS.
vector<vector<int>> tree(parent.size());
for (int i = 1; i < parent.size(); ++i)
tree[parent[i]].push_back(i);
return dfs(tree, 0, 0, s, {{0, 1}});
}
private:
// mask := 26 bits that represent the parity of each character in the alphabet
// on the path from node 0 to node u
long dfs(const vector<vector<int>>& tree, int u, int mask, const string& s,
unordered_map<int, int>&& maskToCount) {
long res = 0;
if (u > 0) {
mask ^= 1 << (s[u] - 'a');
// Consider any u-v path with 1 bit set.
for (int i = 0; i < 26; ++i)
if (const auto it = maskToCount.find(mask ^ (1 << i));
it != maskToCount.cend())
res += it->second;
// Consider u-v path with 0 bit set.
res += maskToCount[mask ^ 0]++;
}
for (const int v : tree[u])
res += dfs(tree, v, mask, s, std::move(maskToCount));
return res;
}
}; /* code provided by PROGIEZ */
2791. Count Paths That Can Form a Palindrome in a Tree LeetCode Solution in Java
class Solution {
public long countPalindromePaths(List<Integer> parent, String s) {
// A valid (u, v) has at most 1 letter with odd frequency on its path. The
// frequency of a letter on the u-v path is equal to the sum of its
// frequencies on the root-u and root-v paths substract twice of its
// frequency on the root-LCA(u, v) path. Considering only the parity
// (even/odd), the part involving root-LCA(u, v) can be ignored, making it
// possible to calculate both parts easily using a simple DFS.
List<Integer>[] tree = new List[parent.size()];
for (int i = 0; i < parent.size(); ++i)
tree[i] = new ArrayList<>();
for (int i = 1; i < parent.size(); ++i)
tree[parent.get(i)].add(i);
return dfs(tree, 0, 0, s, new HashMap<>(Map.of(0, 1)));
}
// mask := 26 bits that represent the parity of each character in the alphabet
// on the path from node 0 to node u
private long dfs(List<Integer>[] tree, int u, int mask, String s,
Map<Integer, Integer> maskToCount) {
long res = 0;
if (u > 0) {
mask ^= 1 << (s.charAt(u) - 'a');
// Consider any u-v path with 1 bit set.
for (int i = 0; i < 26; ++i)
if (maskToCount.containsKey(mask ^ (1 << i)))
res += maskToCount.get(mask ^ (1 << i));
// Consider u-v path with 0 bit set.
res += maskToCount.getOrDefault(mask ^ 0, 0);
maskToCount.merge(mask, 1, Integer::sum);
}
for (final int v : tree[u])
res += dfs(tree, v, mask, s, maskToCount);
return res;
}
} // code provided by PROGIEZ
2791. Count Paths That Can Form a Palindrome in a Tree LeetCode Solution in Python
class Solution:
def countPalindromePaths(self, parent: list[int], s: str) -> int:
# A valid (u, v) has at most 1 letter with odd frequency on its path. The
# frequency of a letter on the u-v path is equal to the sum of its
# frequencies on the root-u and root-v paths substract twice of its
# frequency on the root-LCA(u, v) path. Considering only the parity
# (even/odd), the part involving root-LCA(u, v) can be ignored, making it
# possible to calculate both parts easily using a simple DFS.
tree = [[] for _ in parent]
maskToCount = collections.Counter({0: 1})
for i in range(1, len(parent)):
tree[parent[i]].append(i)
# mask := 26 bits that represent the parity of each character in the alphabet
# on the path from node 0 to node u
def dfs(u: int, mask: int) -> int:
res = 0
if u > 0:
mask ^= 1 << (ord(s[u]) - ord('a'))
# Consider any u-v path with 1 bit set.
for i in range(26):
res += maskToCount[mask ^ (1 << i)]
# Consider u-v path with 0 bit set.
res += maskToCount[mask ^ 0]
maskToCount[mask] += 1
for v in tree[u]:
res += dfs(v, mask)
return res
return dfs(0, 0) # code by PROGIEZ
