3331. Find Subtree Sizes After Changes
MediumView on LeetCode
Time: O(n)
Space: O(n)
Problem Overview
Each non root node may reattach to the closest ancestor that shares its letter, otherwise it keeps its old parent.
Intuition
Each non root node may reattach to the closest ancestor that shares its letter, otherwise it keeps its old parent. Walking every ancestor for every node is quadratic. A DFS of the original tree can keep the latest node seen for each letter on the root to current path. That latest same letter node is exactly the closest matching ancestor. After every edge is rewritten, a second DFS on the new tree fills the subtree sizes.
Algorithm
- 1Build adjacency lists for the original parent array.
- 2DFS from the root while storing the previous path node for the current letter, then set the current node as the latest for that letter.
- 3For each non root node, link it in the new tree to that latest same letter ancestor, or to its original parent when none exists.
- 4Backtrack the letter pointer when leaving the node.
- 5DFS the new tree and store each subtree size in the answer array.
Example Walkthrough
Input: parent = [-1, 0, 0, 1, 1, 1], s = "abaabc"
- 1.Node 2 has letter a and finds ancestor 0 with the same letter, so it reattaches under 0.
- 2.Nodes 3 and 4 keep nearer same letter ancestors when present; otherwise they keep their old parents.
- 3.After the rebuild, the subtree sizes from the new root are 6, 3, 1, 1, 1, 1.
Output: [6, 3, 1, 1, 1, 1]
Common Pitfalls
- •Backtrack the per letter last seen index. Leaving a stale value breaks later sibling paths.
- •If no same letter ancestor exists, keep the original parent. Do not hang the node from the root by default.
- •Compute sizes on the rebuilt tree. Sizes from the original tree are wrong after reparenting.
- •The root never changes parent. Skip rewiring node 0.
3331.cs
C#
// Approach: DFS the original tree while keeping the nearest ancestor for each
// letter on the current path. That ancestor (or the old parent if none) is the
// new parent. Then DFS the rebuilt tree once to fill subtree sizes.
// Time: O(n) Space: O(n)
public class Solution
{
public int[] FindSubtreeSizes(int[] parent, string s)
{
int n = parent.Length;
var tree = new List<int>[n];
var newTree = new List<int>[n];
for (int i = 0; i < n; ++i)
{
tree[i] = new List<int>();
newTree[i] = new List<int>();
}
for (int i = 1; i < n; ++i)
tree[parent[i]].Add(i);
int[] last = new int[26];
Array.Fill(last, -1);
Build(0, parent, s, tree, newTree, last);
int[] ans = new int[n];
DfsSize(0, newTree, ans);
return ans;
}
private void Build(int u, int[] parent, string s, List<int>[] tree,
List<int>[] newTree, int[] last)
{
int c = s[u] - 'a';
int prev = last[c];
if (u != 0)
{
int p = prev != -1 ? prev : parent[u];
newTree[p].Add(u);
}
last[c] = u;
foreach (int v in tree[u])
Build(v, parent, s, tree, newTree, last);
last[c] = prev;
}
private int DfsSize(int u, List<int>[] tree, int[] ans)
{
int sz = 1;
foreach (int v in tree[u])
sz += DfsSize(v, tree, ans);
return ans[u] = sz;
}
}
Was this solution helpful?