Welcome to Subscribe On Youtube
2791. Count Paths That Can Form a Palindrome in a Tree
Description
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.length1 <= n <= 1050 <= parent[i] <= n - 1for alli >= 1parent[0] == -1parentrepresents a valid tree.sconsists of only lowercase English letters.
Solutions
Solution 2: Explicit Stack
Thinking
A path can be rearranged into a palindrome exactly when at most one letter has an odd count. With $n \le 10^5$, enumerating pairs is $O(n^2)$, and recursing into each child from the root is too deep: a chain makes the call depth $n$.
The parity of letters from the root to a node packs into a bitmask, and the parity on the path between two nodes is the XOR of those masks. A palindrome allows at most one bit set. The root mask $0$ is placed in the counter first.
An explicit stack runs a preorder. After a node is popped, each child mask is the parent mask XOR the edge letter. We add the counts of the same mask and of the masks that differ by one bit, then store the child mask and push the child. Each pair is counted only at the node visited later, so the order of siblings does not change the answer.
An explicit stack walks the tree in preorder from the root. The root mask $0$ is stored in the hash map first. For each edge, the child mask is the parent mask XOR the edge letter. Paths that form a palindrome with an already visited node are added to the answer, and the child mask is then recorded.
| The time complexity is $O(n \times | \Sigma | )$ and the space complexity is $O(n)$, where $ | \Sigma | $ is the alphabet size. |
-
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); } } } // Solution 2 class Solution { public long countPalindromePaths(List<Integer> parent, String s) { int n = parent.size(); List<int[]>[] g = new List[n]; 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')}); } Map<Integer, Integer> cnt = new HashMap<>(); cnt.put(0, 1); long ans = 0; Deque<int[]> stk = new ArrayDeque<>(); stk.push(new int[] {0, 0}); while (!stk.isEmpty()) { int[] cur = stk.pop(); int i = cur[0], xor = cur[1]; 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); stk.push(new int[] {j, x}); } } return ans; } } -
class Solution { public: long long countPalindromePaths(vector<int>& parent, string s) { int n = parent.size(); vector<vector<pair<int, int>>> g(n); unordered_map<int, int> cnt; cnt[0] = 1; for (int i = 1; i < n; ++i) { int p = parent[i]; g[p].emplace_back(i, 1 << (s[i] - 'a')); } long long ans = 0; function<void(int, int)> dfs = [&](int i, int xo) { for (auto [j, v] : g[i]) { int x = xo ^ v; ans += cnt[x]; for (int k = 0; k < 26; ++k) { ans += cnt[x ^ (1 << k)]; } ++cnt[x]; dfs(j, x); } }; dfs(0, 0); return ans; } }; // Solution 2 class Solution { public: long long countPalindromePaths(vector<int>& parent, string s) { int n = parent.size(); vector<vector<pair<int, int>>> g(n); for (int i = 1; i < n; ++i) { g[parent[i]].emplace_back(i, 1 << (s[i] - 'a')); } unordered_map<int, int> cnt; cnt[0] = 1; long long ans = 0; vector<pair<int, int>> stk{{0, 0}}; while (!stk.empty()) { auto [i, xo] = stk.back(); stk.pop_back(); for (auto [j, v] : g[i]) { int x = xo ^ v; ans += cnt[x]; for (int k = 0; k < 26; ++k) { ans += cnt[x ^ (1 << k)]; } ++cnt[x]; stk.emplace_back(j, x); } } return ans; } }; -
class Solution: def countPalindromePaths(self, parent: List[int], s: str) -> int: def dfs(i: int, xor: int): nonlocal ans for j, v in g[i]: x = xor ^ v ans += cnt[x] for k in range(26): ans += cnt[x ^ (1 << k)] cnt[x] += 1 dfs(j, x) n = len(parent) g = defaultdict(list) for i in range(1, n): p = parent[i] g[p].append((i, 1 << (ord(s[i]) - ord('a')))) ans = 0 cnt = Counter({0: 1}) dfs(0, 0) return ans # Solution 2 class Solution: def countPalindromePaths(self, parent: List[int], s: str) -> int: n = len(parent) g = [[] for _ in range(n)] for i in range(1, n): g[parent[i]].append((i, 1 << (ord(s[i]) - ord('a')))) ans = 0 cnt = Counter({0: 1}) stk = [(0, 0)] while stk: i, xor = stk.pop() for j, v in g[i]: x = xor ^ v ans += cnt[x] for k in range(26): ans += cnt[x ^ (1 << k)] cnt[x] += 1 stk.append((j, x)) return ans -
func countPalindromePaths(parent []int, s string) (ans int64) { type pair struct{ i, v int } n := len(parent) g := make([][]pair, n) for i := 1; i < n; i++ { p := parent[i] g[p] = append(g[p], pair{i, 1 << (s[i] - 'a')}) } cnt := map[int]int{0: 1} var dfs func(i, xor int) dfs = func(i, xor int) { for _, e := range g[i] { x := xor ^ e.v ans += int64(cnt[x]) for k := 0; k < 26; k++ { ans += int64(cnt[x^(1<<k)]) } cnt[x]++ dfs(e.i, x) } } dfs(0, 0) return } // Solution 2 func countPalindromePaths(parent []int, s string) (ans int64) { type pair struct{ i, v int } n := len(parent) g := make([][]pair, n) for i := 1; i < n; i++ { p := parent[i] g[p] = append(g[p], pair{i, 1 << (s[i] - 'a')}) } cnt := map[int]int{0: 1} stk := []pair{{0, 0}} for len(stk) > 0 { cur := stk[len(stk)-1] stk = stk[:len(stk)-1] for _, e := range g[cur.i] { x := cur.v ^ e.v ans += int64(cnt[x]) for k := 0; k < 26; k++ { ans += int64(cnt[x^(1<<k)]) } cnt[x]++ stk = append(stk, pair{e.i, x}) } } return } -
function countPalindromePaths(parent: number[], s: string): number { const n = parent.length; const g: [number, number][][] = Array.from({ length: n }, () => []); for (let i = 1; i < n; ++i) { g[parent[i]].push([i, 1 << (s.charCodeAt(i) - 97)]); } const cnt: Map<number, number> = new Map(); cnt.set(0, 1); let ans = 0; const dfs = (i: number, xor: number): void => { for (const [j, v] of g[i]) { const x = xor ^ v; ans += cnt.get(x) || 0; for (let k = 0; k < 26; ++k) { ans += cnt.get(x ^ (1 << k)) || 0; } cnt.set(x, (cnt.get(x) || 0) + 1); dfs(j, x); } }; dfs(0, 0); return ans; } // Solution 2 function countPalindromePaths(parent: number[], s: string): number { const n = parent.length; const g: [number, number][][] = Array.from({ length: n }, () => []); for (let i = 1; i < n; ++i) { g[parent[i]].push([i, 1 << (s.charCodeAt(i) - 97)]); } const cnt: Map<number, number> = new Map(); cnt.set(0, 1); let ans = 0; const stk: [number, number][] = [[0, 0]]; while (stk.length) { const [i, xor] = stk.pop()!; for (const [j, v] of g[i]) { const x = xor ^ v; ans += cnt.get(x) || 0; for (let k = 0; k < 26; ++k) { ans += cnt.get(x ^ (1 << k)) || 0; } cnt.set(x, (cnt.get(x) || 0) + 1); stk.push([j, x]); } } return ans; }