Find Subtree Sizes After Changes

Medium
1725.

Find Subtree Sizes After Changes

Find Subtree Sizes After Changes is a medium coding problem on arrays, strings and hash table, asked in Google interviews.

A tree has n nodes numbered 0 to n - 1 and is rooted at node 0. It is given by parent, where parent[i] is the parent of node i and parent[0] = -1. Node i carries the letter s[i].

All at once, for every node x from 1 to n - 1: find the closest ancestor y of x (in the original tree) with s[y] == s[x]. If such a y exists, cut the edge between x and its parent and make y the new parent of x. If none exists, x keeps its parent.

Return an array answer of length n where answer[i] is the number of nodes in the subtree of node i in the final tree.

Example 1

Input
parent = [-1,0,0,1,1,1], s = "abaabc"
Output
[6,3,1,1,1,1]
Explanation
Node 3 ('a') has the ancestor 0 ('a'), so it moves under node 0. Every other node keeps its parent.

Example 2

Input
parent = [-1,0,4,0,1], s = "abbba"
Output
[5,2,1,1,1]
Explanation
Node 4 ('a') moves under node 0 and node 2 ('b') moves under node 1; node 1 then holds nodes 1 and 2.

Example 3

Input
parent = [-1], s = "z"
Output
[1]

Constraints

  • n == parent.length == s.length
  • 1 <= n <= 10^5
  • 0 <= parent[i] <= n - 1 for all i >= 1
  • parent[0] == -1
  • parent represents a valid tree
  • s consists only of lowercase English letters
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} parent
 * @param {string} s
 * @return {number[]}
 */
var findSubtreeSizes = function(parent, s) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Find Subtree Sizes After Changes — Problem & Solution

Find Subtree Sizes After Changes solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.

Find Subtree Sizes After Changes is a medium coding problem on arrays, strings and hash table, asked in Google interviews.

Problem statement

A tree has n nodes numbered 0 to n - 1 and is rooted at node 0. It is given by parent, where parent[i] is the parent of node i and parent[0] = -1. Node i carries the letter s[i].

All at once, for every node x from 1 to n - 1: find the closest ancestor y of x (in the original tree) with s[y] == s[x]. If such a y exists, cut the edge between x and its parent and make y the new parent of x. If none exists, x keeps its parent.

Return an array answer of length n where answer[i] is the number of nodes in the subtree of node i in the final tree.

Example 1

Input: parent = [-1,0,0,1,1,1], s = "abaabc"
Output: [6,3,1,1,1,1]
Explanation: Node 3 ('a') has the ancestor 0 ('a'), so it moves under node 0. Every other node keeps its parent.

Example 2

Input: parent = [-1,0,4,0,1], s = "abbba"
Output: [5,2,1,1,1]
Explanation: Node 4 ('a') moves under node 0 and node 2 ('b') moves under node 1; node 1 then holds nodes 1 and 2.

Example 3

Input: parent = [-1], s = "z"
Output: [1]

Constraints

  • n == parent.length == s.length
  • 1 <= n <= 10^5
  • 0 <= parent[i] <= n - 1 for all i >= 1
  • parent[0] == -1
  • parent represents a valid tree
  • s consists only of lowercase English letters

Hints for Find Subtree Sizes After Changes

  1. Hint 1

    The changes are simultaneous and use the original tree, so every node's new parent can be decided independently.

  2. Hint 2

    Walk the tree depth-first. If you keep, for every letter, the deepest node with that letter on the current root-to-node path, the closest matching ancestor is just a lookup.

  3. Hint 3

    Remember the old entry when you overwrite a letter's slot on entering a node, and restore it when you leave. Then a new parent is always an old ancestor, so a reverse pre-order pass adds up the new subtree sizes.

How to solve Find Subtree Sizes After Changes

A depth-first walk keeps the current root-to-node path; a 26-slot table holding the deepest node of each letter on that path answers "closest ancestor with the same letter" in O(1). Since the new parent is an ancestor, the pre-order of the original tree still lists every new parent before its children.

Approach

  1. Build the children lists from parent.
  2. DFS from 0 with an explicit stack. On entering x (not the root): if last[s[x]] is set, the new parent of x is that node. Save the old last[s[x]], set it to x, and record x in pre-order.
  3. On leaving x, restore last[s[x]] to the saved value.
  4. Set every size to 1 and walk the pre-order backwards, adding size[x] to size[newParent[x]].

Why it works

When x is entered, the table holds exactly the nodes on the path from the root to x's parent, the deepest one per letter, because every node leaving the path restores what it overwrote. So the lookup is the closest matching ancestor in the original tree, as the simultaneous rule requires. The new parent precedes x in pre-order, so the backward accumulation sees every child before its parent.

Complexity

  • Time — O(n)
  • Space — O(n)

Pitfalls

  • Do not apply the moves one at a time and look up ancestors in the changing tree — the rule is defined on the original tree.
  • Forgetting to restore the letter slot on exit lets a node in one branch adopt a node from a sibling branch.
  • The root never changes its parent.

Reference solution

Python

from typing import List

def findSubtreeSizes(parent: List[int], s: str) -> List[int]:
    n = len(parent)
    children = [[] for _ in range(n)]
    for i in range(1, n):
        children[parent[i]].append(i)
    last = [-1] * 26
    saved = [-1] * n
    newp = parent[:]
    pre = []
    stack = [0]
    while stack:
        x = stack.pop()
        if x >= 0:
            c = ord(s[x]) - 97
            if x != 0 and last[c] != -1:
                newp[x] = last[c]
            saved[x] = last[c]
            last[c] = x
            pre.append(x)
            stack.append(~x)
            stack.extend(children[x])
        else:
            x = ~x
            last[ord(s[x]) - 97] = saved[x]
    size = [1] * n
    for x in reversed(pre):
        if x != 0:
            size[newp[x]] += size[x]
    return size

Java

public static int[] findSubtreeSizes(int[] parent, String s) {
    int n = parent.length;
    List<List<Integer>> children = new ArrayList<>();
    for (int i = 0; i < n; i++) children.add(new ArrayList<>());
    for (int i = 1; i < n; i++) children.get(parent[i]).add(i);
    int[] last = new int[26];
    Arrays.fill(last, -1);
    int[] saved = new int[n], newp = parent.clone(), size = new int[n], pre = new int[n];
    Arrays.fill(size, 1);
    int[] stack = new int[2 * n + 1];
    int top = 0, cnt = 0;
    stack[top++] = 0;
    while (top > 0) {
        int x = stack[--top];
        if (x >= 0) {
            int c = s.charAt(x) - 'a';
            if (x != 0 && last[c] != -1) newp[x] = last[c];
            saved[x] = last[c];
            last[c] = x;
            pre[cnt++] = x;
            stack[top++] = -x - 1;
            for (int y : children.get(x)) stack[top++] = y;
        } else {
            int y = -x - 1;
            last[s.charAt(y) - 'a'] = saved[y];
        }
    }
    for (int t = n - 1; t > 0; t--) size[newp[pre[t]]] += size[pre[t]];
    return size;
}

C++

vector<int> findSubtreeSizes(vector<int>& parent, string s) {
    int n = parent.size();
    vector<vector<int>> children(n);
    for (int i = 1; i < n; i++) children[parent[i]].push_back(i);
    vector<int> last(26, -1), saved(n, -1), newp(parent), size(n, 1), pre, stack = {0};
    while (!stack.empty()) {
        int x = stack.back();
        stack.pop_back();
        if (x >= 0) {
            int c = s[x] - 'a';
            if (x != 0 && last[c] != -1) newp[x] = last[c];
            saved[x] = last[c];
            last[c] = x;
            pre.push_back(x);
            stack.push_back(-x - 1);
            for (int y : children[x]) stack.push_back(y);
        } else {
            int y = -x - 1;
            last[s[y] - 'a'] = saved[y];
        }
    }
    for (int t = n - 1; t > 0; t--) size[newp[pre[t]]] += size[pre[t]];
    return size;
}

JavaScript

var findSubtreeSizes = function(parent, s) {
    var n = parent.length;
    var children = [], saved = [], newp = [], size = [];
    for (var i = 0; i < n; i++) { children.push([]); saved.push(-1); newp.push(parent[i]); size.push(1); }
    for (var j = 1; j < n; j++) children[parent[j]].push(j);
    var last = [];
    for (var c = 0; c < 26; c++) last.push(-1);
    var pre = [], stack = [0];
    while (stack.length > 0) {
        var x = stack.pop();
        if (x >= 0) {
            var ch = s.charCodeAt(x) - 97;
            if (x !== 0 && last[ch] !== -1) newp[x] = last[ch];
            saved[x] = last[ch];
            last[ch] = x;
            pre.push(x);
            stack.push(-x - 1);
            for (var k = 0; k < children[x].length; k++) stack.push(children[x][k]);
        } else {
            var y = -x - 1;
            last[s.charCodeAt(y) - 97] = saved[y];
        }
    }
    for (var t = n - 1; t > 0; t--) size[newp[pre[t]]] += size[pre[t]];
    return size;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Strings