1import java.util.List;
2import java.util.ArrayList;
3import java.util.Arrays;
4
5class Solution {
6    private List<Integer>[] adjacencyList;  // Represents graph edges as adjacency list
7    private List<Integer>[] characterIndices;  // Stores indices of characters in the string
8    private char[] charArray;  // Character array of the input string
9    private int[] subtreeSizes;  // Array to hold resulting subtree sizes
10
11    // Method to find subtree sizes for each node based on string properties
12    public int[] findSubtreeSizes(int[] parent, String s) {
13        int n = s.length();  // Total number of nodes
14
15        adjacencyList = new List[n];  // Initialize the adjacency list
16        characterIndices = new List[26];  // Initialize arrays to store character indices ('a' to 'z')
17
18        charArray = s.toCharArray();  // Convert string to character array
19
20        // Initialize each element of adjacency list and characterIndices list
21        Arrays.setAll(adjacencyList, k -> new ArrayList<>());
22        Arrays.setAll(characterIndices, k -> new ArrayList<>());
23
24        // Build the adjacency list from parent-child relationships
25        for (int i = 1; i < n; ++i) {
26            adjacencyList[parent[i]].add(i);  // Add child to parent's list
27        }
28
29        subtreeSizes = new int[n];  // Initialize subtree sizes array
30
31        dfs(0, -1);  // Start DFS from root node
32
33        return subtreeSizes;  // Return computed subtree sizes
34    }
35
36    // Depth First Search recursive method to compute subtree sizes
37    private void dfs(int currentNode, int parentNode) {
38        subtreeSizes[currentNode] = 1;  // Start with size 1 for the node itself
39        int charIndex = charArray[currentNode] - 'a';  // Find the character index (0 for 'a', 1 for 'b', etc.)
40      
41        characterIndices[charIndex].add(currentNode);  // Add current node to the list of indices for its character
42
43        // Recursively traverse each child node
44        for (int childNode : adjacencyList[currentNode]) {
45            dfs(childNode, currentNode);  // DFS on child
46        }
47
48        // Fetch the 'parent node' in the context of the current character path
49        int previousNode = characterIndices[charIndex].size() > 1 ? 
50                characterIndices[charIndex].get(characterIndices[charIndex].size() - 2) : parentNode;
51      
52        // If valid previous node exists, add current subtree size to it
53        if (previousNode >= 0) {
54            subtreeSizes[previousNode] += subtreeSizes[currentNode];
55        }
56
57        // Remove current node from the list of character indices
58        characterIndices[charIndex].remove(characterIndices[charIndex].size() - 1);
59    }
60}
61

1#include <vector>
2#include <string>
3using namespace std;
4
5class Solution {
6public:
7    vector<int> findSubtreeSizes(vector<int>& parent, string s) {
8        int n = s.size();
9      
10        // Graph to store children of each node
11        vector<vector<int>> graph(n);
12      
13        // An array to keep track of nodes for each character in the string
14        vector<vector<int>> charNodes(26);
15      
16        // Build the graph from the parent list
17        for (int i = 1; i < n; ++i) {
18            graph[parent[i]].push_back(i);
19        }
20      
21        // Resultant vector to store subtree sizes
22        vector<int> result(n);
23      
24        // Recursive lambda function for Depth First Search
25        function<void(int, int)> dfs = [&](int node, int parent) {
26            // Initialize current node size as 1 (counting itself)
27            result[node] = 1;
28          
29            // Get the character index for the current node
30            int charIndex = s[node] - 'a';
31          
32            // Add the current node to the corresponding character's list
33            charNodes[charIndex].push_back(node);
34          
35            // Recursively visit each child
36            for (int child : graph[node]) {
37                dfs(child, node);
38            }
39          
40            // Find the parent node for this character or default to the given parent
41            int prevNode = charNodes[charIndex].size() > 1 ? charNodes[charIndex][charNodes[charIndex].size() - 2] : parent;
42          
43            // Add the current subtree size to the previous node in the character's list
44            if (prevNode >= 0) {
45                result[prevNode] += result[node];
46            }
47          
48            // Remove the current node from the character's list
49            charNodes[charIndex].pop_back();
50        };
51      
52        // Start DFS from the root node with no parent (-1)
53        dfs(0, -1);
54      
55        // Return the result containing sizes of subtrees with the same character
56        return result;
57    }
58};
59

1function findSubtreeSizes(parent: number[], s: string): number[] {
2    const n = parent.length;  // Number of nodes in the tree
3    const g: number[][] = Array.from({ length: n }, () => []); // Adjacency list for the tree
4    const d: number[][] = Array.from({ length: 26 }, () => []); // Array to keep track of character occurrences
5
6    // Build the tree using the parent array
7    for (let i = 1; i < n; ++i) {
8        g[parent[i]].push(i);
9    }
10
11    const ans: number[] = Array(n).fill(1); // Initialize subtree sizes, each node itself is a subtree
12
13    // Depth First Search to compute subtree sizes
14    const dfs = (current: number, predecessor: number): void => {
15        const charIndex = s.charCodeAt(current) - 97; // Convert character to index
16        d[charIndex].push(current); // Add current node to the character index list
17
18        // Explore children nodes
19        for (const child of g[current]) {
20            dfs(child, current);
21        }
22
23        // Find previous node with the same character or use predecessor
24        const prev = d[charIndex].length > 1 ? d[charIndex][d[charIndex].length - 2] : predecessor;
25      
26        if (prev >= 0) {
27            ans[prev] += ans[current]; // Update the size of the subtree
28        }
29
30        d[charIndex].pop(); // Remove current node from the character index list
31    };
32
33    dfs(0, -1); // Start DFS from the root node
34    return ans; // Return calculated subtree sizes
35}
36