Check if DFS Strings Are Palindromes

• Create an adjacency list adj from the parent array to represent the tree. Since children are added based on their node index i, they will be naturally sorted.
• Initialize a boolean array answer of size n.
• Iterate through each node i from 0 to n-1.
• For each i:
  • Create an empty StringBuilder to store the dfsStr.
  • Call a recursive helper function, say buildDfsStr(i, adj, s, dfsStr), to construct the string.
  • The buildDfsStr function performs a post-order traversal on the subtree rooted at the given node. It first makes recursive calls for all children (in increasing order of their indices) and then appends the character of the current node to the StringBuilder.
  • After the string is built, convert it to a String.
  • Check if the resulting string is a palindrome. This can be done with a two-pointer approach, comparing characters from the start and end moving inwards.
  • Store the result of the palindrome check in answer[i].
• Finally, return the answer array.

First, we need a convenient representation of the tree. We can convert the given parent array into an adjacency list, where adj[u] stores a list of all children of node u. The problem specifies that children should be visited in increasing order of their numbers, and building the adjacency list by iterating from i=1 to n-1 naturally achieves this.

Next, we loop through every node i from 0 to n-1. In each iteration, we initiate the process of building dfsStr for the subtree rooted at i. A recursive DFS function is used for this. This function takes the current node u, the adjacency list, the character string s, and a StringBuilder as arguments. It recursively calls itself for each child of u and then appends s.charAt(u) to the StringBuilder. This is a classic post-order traversal.

After the recursive calls starting from i are complete, the StringBuilder will contain the full dfsStr. We then check if this string is a palindrome. A simple and efficient way to do this is using a two-pointer technique. One pointer starts at the beginning of the string, and the other at the end. We move them towards the center, checking if the characters at their positions are always equal. If we find a mismatch, it's not a palindrome. If the pointers meet or cross without any mismatches, it is a palindrome.

The boolean result of this check is stored in answer[i], and after iterating through all nodes, the answer array is returned.

1import java.util.ArrayList;2import java.util.List;3 4class Solution {5    public boolean[] checkDfsPalindromes(int[] parent, String s) {6        int n = parent.length;7        List<List<Integer>> adj = new ArrayList<>();8        for (int i = 0; i < n; i++) {9            adj.add(new ArrayList<>());10        }11        for (int i = 1; i < n; i++) {12            adj.get(parent[i]).add(i);13        }14 15        boolean[] answer = new boolean[n];16        for (int i = 0; i < n; i++) {17            StringBuilder dfsStr = new StringBuilder();18            generateDfsString(i, adj, s, dfsStr);19            answer[i] = isPalindrome(dfsStr.toString());20        }21        return answer;22    }23 24    private void generateDfsString(int u, List<List<Integer>> adj, String s, StringBuilder sb) {25        for (int v : adj.get(u)) {26            generateDfsString(v, adj, s, sb);27        }28        sb.append(s.charAt(u));29    }30 31    private boolean isPalindrome(String str) {32        int left = 0;33        int right = str.length() - 1;34        while (left < right) {35            if (str.charAt(left) != str.charAt(right)) {36                return false;37            }38            left++;39            right--;40        }41        return true;42    }43}

• Select two different pairs of prime base and large prime modulus, e.g., (P1, M1) and (P2, M2), to minimize hash collisions.
• Precompute the powers of P1 and P2 modulo their respective moduli up to n and store them in arrays for O(1) access.
• Build the adjacency list representation of the tree from the parent array.
• Create arrays to store the length (len), forward hashes (h1, h2), and reverse hashes (rh1, rh2) for the dfsStr of each node's subtree.
• Perform a single post-order traversal of the entire tree, starting from the root (node 0). A recursive DFS function postOrder(u) is suitable for this.
• Inside postOrder(u), after the recursive calls for all children of u have returned:
  • Compute len[u], the size of the subtree at u, by summing the lengths of its children's subtrees and adding 1 for u itself.
  • Compute the forward hashes h1[u] and h2[u]. This is done by combining the forward hashes of its children (in increasing order of child index) and then appending the character s[u].
  • Compute the reverse hashes rh1[u] and rh2[u]. This is done by starting with the character s[u] and then combining the reverse hashes of its children (in decreasing order of child index).
  • A string is a palindrome if its forward hash equals its reverse hash. Check if h1[u] == rh1[u] and h2[u] == rh2[u]. Set answer[u] to the result of this check.
• After the traversal is complete, return the answer array.

This approach avoids the O(N^2) complexity by calculating hashes for dfsStr(u) and reverse(dfsStr(u)) for every node u in one pass. Let's denote the forward hash as h[u] and the reverse hash as rh[u]. A string is a palindrome if h[u] == rh[u].

We use a post-order traversal (DFS) because to compute the hashes for a node u, we first need the hashes and lengths for all of its children. The traversal computes the following for each node u:

1. len[u]: The length of dfsStr(u), which is simply the size of the subtree rooted at u.
2. h[u]: The hash of dfsStr(u) = dfsStr(c1) + ... + dfsStr(ck) + s[u]. This is computed by combining the hashes of its children's strings h[c1], ..., h[ck] in order, and then incorporating s[u].
3. rh[u]: The hash of reverse(dfsStr(u)) = s[u] + reverse(dfsStr(ck)) + ... + reverse(dfsStr(c1)). This is computed by starting with s[u] and then combining the reverse hashes of its children rh[ck], ..., rh[c1] in reverse order.

The hash of a concatenated string A + B is (hash(A) + hash(B) * p^length(A)) % M. We use this formula to combine the children's hashes. To make the solution robust against collisions, we use two independent hash functions with different bases and moduli.

1import java.util.ArrayList;2import java.util.List;3 4class Solution {5    private List<List<Integer>> adj;6    private String s;7    private boolean[] answer;8    private long[] p1_pow, p2_pow;9    private long[] h1, h2, rh1, rh2;10    private int[] len;11    private final long P1 = 31, M1 = 1_000_000_007;12    private final long P2 = 37, M2 = 1_000_000_009;13 14    public boolean[] checkDfsPalindromes(int[] parent, String s) {15        int n = parent.length;16        this.s = s;17        this.adj = new ArrayList<>();18        for (int i = 0; i < n; i++) {19            adj.add(new ArrayList<>());20        }21        for (int i = 1; i < n; i++) {22            adj.get(parent[i]).add(i);23        }24 25        this.answer = new boolean[n];26        this.p1_pow = new long[n + 1];27        this.p2_pow = new long[n + 1];28        this.h1 = new long[n];29        this.h2 = new long[n];30        this.rh1 = new long[n];31        this.rh2 = new long[n];32        this.len = new int[n];33 34        p1_pow[0] = 1;35        p2_pow[0] = 1;36        for (int i = 1; i <= n; i++) {37            p1_pow[i] = (p1_pow[i - 1] * P1) % M1;38            p2_pow[i] = (p2_pow[i - 1] * P2) % M2;39        }40 41        postOrder(0);42        return answer;43    }44 45    private void postOrder(int u) {46        for (int v : adj.get(u)) {47            postOrder(v);48        }49 50        // Compute forward hash51        long current_h1 = 0, current_h2 = 0;52        int current_len = 0;53        for (int v : adj.get(u)) {54            current_h1 = (current_h1 + (h1[v] * p1_pow[current_len]) % M1) % M1;55            current_h2 = (current_h2 + (h2[v] * p2_pow[current_len]) % M2) % M2;56            current_len += len[v];57        }58        long char_val = s.charAt(u) - 'a' + 1;59        h1[u] = (current_h1 + (char_val * p1_pow[current_len]) % M1) % M1;60        h2[u] = (current_h2 + (char_val * p2_pow[current_len]) % M2) % M2;61        62        // Compute reverse hash63        long current_rh1 = char_val, current_rh2 = char_val;64        int current_rev_len = 1;65        List<Integer> children = adj.get(u);66        for (int i = children.size() - 1; i >= 0; i--) {67            int v = children.get(i);68            current_rh1 = (current_rh1 + (rh1[v] * p1_pow[current_rev_len]) % M1) % M1;69            current_rh2 = (current_rh2 + (rh2[v] * p2_pow[current_rev_len]) % M2) % M2;70            current_rev_len += len[v];71        }72        rh1[u] = current_rh1;73        rh2[u] = current_rh2;74 75        len[u] = current_len + 1;76 77        answer[u] = (h1[u] == rh1[u] && h2[u] == rh2[u]);78    }79}