# Check if DFS Strings Are Palindromes
**Difficulty:** HARD
[External](https://leetcode.com/problems/check-if-dfs-strings-are-palindromes)
Canonical: https://scaleengineer.com/dsa/problems/check-if-dfs-strings-are-palindromes
**Patterns:** [Hash Function](https://scaleengineer.com/dsa/patterns/hash-function)
**Algorithms:** [Depth-First Search](https://scaleengineer.com/algorithms/depth-first-search)
**Data structures:** Array, Hash Table, String, Tree
---
## Problem
You are given a tree rooted at node 0, consisting of `n` nodes numbered from `0` to `n - 1`. The tree is represented by an 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 node `i`.

Consider an empty string `dfsStr`, and define a recursive function `dfs(int x)` that takes a node `x` as a parameter and performs the following steps in order:

* Iterate over each child `y` of `x` **in increasing order of their numbers**, and call `dfs(y)`.
* Add the character `s[x]` to the end of the string `dfsStr`.

**Note** that `dfsStr` is shared across all recursive calls of `dfs`.

You need to find a boolean array `answer` of size `n`, where for each index `i` from `0` to `n - 1`, you do the following:

* Empty the string `dfsStr` and call `dfs(i)`.
* If the resulting string `dfsStr` is a palindrome, then set `answer[i]` to `true`. Otherwise, set `answer[i]` to `false`.

Return the array `answer`.

**Example 1:**

![](https://assets.glich.co/dsa/check-if-dfs-strings-are-palindromes/image0.png) 

**Input:** parent = \[-1,0,0,1,1,2\], s = "aababa"

**Output:** \[true,true,false,true,true,true\]

**Explanation:**

* Calling `dfs(0)` results in the string `dfsStr = "abaaba"`, which is a palindrome.
* Calling `dfs(1)` results in the string `dfsStr = "aba"`, which is a palindrome.
* Calling `dfs(2)` results in the string `dfsStr = "ab"`, which is **not** a palindrome.
* Calling `dfs(3)` results in the string `dfsStr = "a"`, which is a palindrome.
* Calling `dfs(4)` results in the string `dfsStr = "b"`, which is a palindrome.
* Calling `dfs(5)` results in the string `dfsStr = "a"`, which is a palindrome.

**Example 2:**

![](https://assets.glich.co/dsa/check-if-dfs-strings-are-palindromes/image1.png) 

**Input:** parent = \[-1,0,0,0,0\], s = "aabcb"

**Output:** \[true,true,true,true,true\]

**Explanation:**

Every call on `dfs(x)` results in a palindrome string.

**Constraints:**

* `n == parent.length == s.length`
* `1 <= n <= 105`
* `0 <= parent[i] <= n - 1` for all `i >= 1`.
* `parent[0] == -1`
* `parent` represents a valid tree.
* `s` consists only of lowercase English letters.

# Approaches
## Brute-Force Simulation
The most straightforward approach is to directly simulate the process described in the problem. For each node `i` in the tree, we can perform the specified DFS traversal starting from `i` to generate the corresponding `dfsStr`. Once the string is generated, we can check if it's a palindrome. We repeat this for all `n` nodes.
**Time:** O(N^2). The main loop runs N times. Inside the loop, we perform a DFS on the subtree of node `i`. Let `size(i)` be the size of the subtree. The DFS and palindrome check both take O(size(i)) time. The total time is the sum of `size(i)` for all `i`. In the worst case of a line graph (e.g., 0-1-2-...-n-1), the sum is N + (N-1) + ... + 1, which is O(N^2). · **Space:** O(N). The space is dominated by the adjacency list (O(N)), the recursion stack depth (which can be O(N) in a skewed tree), and the `dfsStr` which can have a length up to N.
**Pros:** Simple to understand and implement as it directly follows the problem statement.; Correct for small inputs.
**Cons:** The time complexity of O(N^2) is too slow for the given constraints (N up to 10^5) and will result in a Time Limit Exceeded error on larger test cases.
### Explanation
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.

```java
import java.util.ArrayList;
import java.util.List;

class Solution {
    public boolean[] checkDfsPalindromes(int[] parent, String s) {
        int n = parent.length;
        List<List<Integer>> adj = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            adj.add(new ArrayList<>());
        }
        for (int i = 1; i < n; i++) {
            adj.get(parent[i]).add(i);
        }

        boolean[] answer = new boolean[n];
        for (int i = 0; i < n; i++) {
            StringBuilder dfsStr = new StringBuilder();
            generateDfsString(i, adj, s, dfsStr);
            answer[i] = isPalindrome(dfsStr.toString());
        }
        return answer;
    }

    private void generateDfsString(int u, List<List<Integer>> adj, String s, StringBuilder sb) {
        for (int v : adj.get(u)) {
            generateDfsString(v, adj, s, sb);
        }
        sb.append(s.charAt(u));
    }

    private boolean isPalindrome(String str) {
        int left = 0;
        int right = str.length() - 1;
        while (left < right) {
            if (str.charAt(left) != str.charAt(right)) {
                return false;
            }
            left++;
            right--;
        }
        return true;
    }
}
```
### Algorithm
- 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.

## Post-order Traversal with String Hashing
The brute-force approach is slow because it repeatedly generates and compares strings. A much more efficient method is to use polynomial rolling hash to represent the strings. Hashing allows us to compute a unique (with high probability) numerical signature for each string and its reverse. We can then check for palindromes by simply comparing these numerical hash values, which is an O(1) operation.

The key insight is that the hash of `dfsStr(u)` and its reverse can be computed efficiently for all nodes `u` in a single post-order traversal of the tree. The hash for a parent node can be constructed from the pre-computed hashes of its children.
**Time:** O(N). We perform a single DFS traversal, visiting each node and edge exactly once. The precomputation of powers also takes O(N). The work done at each node during the traversal is proportional to its number of children. The sum of children over all nodes is the number of edges, N-1. Thus, the total time is linear. · **Space:** O(N). We need O(N) space for the adjacency list, the recursion stack (O(H) where H is tree height, O(N) in worst case), and several arrays of size N to store lengths and hash values.
**Pros:** Optimal time complexity of O(N), which is very efficient and passes for large constraints.; Solves the problem in a single pass over the tree.
**Cons:** The implementation is more complex than the brute-force approach.; It relies on polynomial rolling hash, which has a theoretical, albeit extremely small, probability of collision. Using two hash functions makes this probability negligible for practical purposes.
### Explanation
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.

```java
import java.util.ArrayList;
import java.util.List;

class Solution {
    private List<List<Integer>> adj;
    private String s;
    private boolean[] answer;
    private long[] p1_pow, p2_pow;
    private long[] h1, h2, rh1, rh2;
    private int[] len;
    private final long P1 = 31, M1 = 1_000_000_007;
    private final long P2 = 37, M2 = 1_000_000_009;

    public boolean[] checkDfsPalindromes(int[] parent, String s) {
        int n = parent.length;
        this.s = s;
        this.adj = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            adj.add(new ArrayList<>());
        }
        for (int i = 1; i < n; i++) {
            adj.get(parent[i]).add(i);
        }

        this.answer = new boolean[n];
        this.p1_pow = new long[n + 1];
        this.p2_pow = new long[n + 1];
        this.h1 = new long[n];
        this.h2 = new long[n];
        this.rh1 = new long[n];
        this.rh2 = new long[n];
        this.len = new int[n];

        p1_pow[0] = 1;
        p2_pow[0] = 1;
        for (int i = 1; i <= n; i++) {
            p1_pow[i] = (p1_pow[i - 1] * P1) % M1;
            p2_pow[i] = (p2_pow[i - 1] * P2) % M2;
        }

        postOrder(0);
        return answer;
    }

    private void postOrder(int u) {
        for (int v : adj.get(u)) {
            postOrder(v);
        }

        // Compute forward hash
        long current_h1 = 0, current_h2 = 0;
        int current_len = 0;
        for (int v : adj.get(u)) {
            current_h1 = (current_h1 + (h1[v] * p1_pow[current_len]) % M1) % M1;
            current_h2 = (current_h2 + (h2[v] * p2_pow[current_len]) % M2) % M2;
            current_len += len[v];
        }
        long char_val = s.charAt(u) - 'a' + 1;
        h1[u] = (current_h1 + (char_val * p1_pow[current_len]) % M1) % M1;
        h2[u] = (current_h2 + (char_val * p2_pow[current_len]) % M2) % M2;
        
        // Compute reverse hash
        long current_rh1 = char_val, current_rh2 = char_val;
        int current_rev_len = 1;
        List<Integer> children = adj.get(u);
        for (int i = children.size() - 1; i >= 0; i--) {
            int v = children.get(i);
            current_rh1 = (current_rh1 + (rh1[v] * p1_pow[current_rev_len]) % M1) % M1;
            current_rh2 = (current_rh2 + (rh2[v] * p2_pow[current_rev_len]) % M2) % M2;
            current_rev_len += len[v];
        }
        rh1[u] = current_rh1;
        rh2[u] = current_rh2;

        len[u] = current_len + 1;

        answer[u] = (h1[u] == rh1[u] && h2[u] == rh2[u]);
    }
}
```
### Algorithm
- 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.

# Solutions
### Java

```java
class Hashing { private final long [] p ; private final long [] h ; private final long mod ; public Hashing ( String word , long base , int mod ) { int n = word . length (); p = new long [ n + 1 ]; h = new long [ n + 1 ]; p [ 0 ] = 1 ; this . mod = mod ; for ( int i = 1 ; i <= n ; i ++) { p [ i ] = p [ i - 1 ] * base % mod ; h [ i ] = ( h [ i - 1 ] * base + word . charAt ( i - 1 )) % mod ; } } public long query ( int l , int r ) { return ( h [ r ] - h [ l - 1 ] * p [ r - l + 1 ] % mod + mod ) % mod ; } } class Solution { private char [] s ; private int [][] pos ; private List < Integer >[] g ; private StringBuilder dfsStr = new StringBuilder (); public boolean [] findAnswer ( int [] parent , String s ) { this . s = s . toCharArray (); int n = s . length (); g = new List [ n ]; pos = new int [ n ][ 0 ]; Arrays . setAll ( g , k -> new ArrayList <>()); for ( int i = 1 ; i < n ; ++ i ) { g [ parent [ i ]]. add ( i ); } dfs ( 0 ); final int base = 13331 ; final int mod = 998244353 ; Hashing h1 = new Hashing ( dfsStr . toString (), base , mod ); Hashing h2 = new Hashing ( new StringBuilder ( dfsStr ). reverse (). toString (), base , mod ); boolean [] ans = new boolean [ n ]; for ( int i = 0 ; i < n ; ++ i ) { int l = pos [ i ][ 0 ], r = pos [ i ][ 1 ]; int k = r - l + 1 ; long v1 = h1 . query ( l , l + k / 2 - 1 ); long v2 = h2 . query ( n + 1 - r , n + 1 - r + k / 2 - 1 ); ans [ i ] = v1 == v2 ; } return ans ; } private void dfs ( int i ) { int l = dfsStr . length () + 1 ; for ( int j : g [ i ]) { dfs ( j ); } dfsStr . append ( s [ i ]); int r = dfsStr . length (); pos [ i ] = new int [] { l , r }; } }
```

### CPP

```cpp
class Hashing { private: vector < long long > p ; vector < long long > h ; long long mod ; public: Hashing ( string word , long long base , int mod ) { int n = word . size (); p . resize ( n + 1 ); h . resize ( n + 1 ); p [ 0 ] = 1 ; this -> mod = mod ; for ( int i = 1 ; i <= n ; i ++ ) { p [ i ] = ( p [ i - 1 ] * base ) % mod ; h [ i ] = ( h [ i - 1 ] * base + word [ i - 1 ] - 'a' ) % mod ; } } long long query ( int l , int r ) { return ( h [ r ] - h [ l - 1 ] * p [ r - l + 1 ] % mod + mod ) % mod ; } }; class Solution { public: vector < bool > findAnswer ( vector < int >& parent , string s ) { int n = s . size (); vector < int > g [ n ]; for ( int i = 1 ; i < n ; ++ i ) { g [ parent [ i ]]. push_back ( i ); } string dfsStr ; vector < pair < int , int >> pos ( n ); auto dfs = [ & ]( auto && dfs , int i ) -> void { int l = dfsStr . size () + 1 ; for ( int j : g [ i ]) { dfs ( dfs , j ); } dfsStr . push_back ( s [ i ]); int r = dfsStr . size (); pos [ i ] = { l , r }; }; dfs ( dfs , 0 ); const int base = 13331 ; const int mod = 998244353 ; Hashing h1 ( dfsStr , base , mod ); reverse ( dfsStr . begin (), dfsStr . end ()); Hashing h2 ( dfsStr , base , mod ); vector < bool > ans ( n ); for ( int i = 0 ; i < n ; ++ i ) { auto [ l , r ] = pos [ i ]; int k = r - l + 1 ; long long v1 = h1 . query ( l , l + k / 2 - 1 ); long long v2 = h2 . query ( n - r + 1 , n - r + 1 + k / 2 - 1 ); ans [ i ] = v1 == v2 ; } return ans ; } };
```

### Python

```python
class Hashing : __slots__ = [ "mod" , "h" , "p" ] def __init__ ( self , s : List [ str ], base : int , mod : int ): self . mod = mod self . h = [ 0 ] * ( len ( s ) + 1 ) self . p = [ 1 ] * ( len ( s ) + 1 ) for i in range ( 1 , len ( s ) + 1 ): self . h [ i ] = ( self . h [ i - 1 ] * base + ord ( s [ i - 1 ])) % mod self . p [ i ] = ( self . p [ i - 1 ] * base ) % mod def query ( self , l : int , r : int ) -> int : return ( self . h [ r ] - self . h [ l - 1 ] * self . p [ r - l + 1 ]) % self . mod class Solution : def findAnswer ( self , parent : List [ int ], s : str ) -> List [ bool ]: def dfs ( i : int ): l = len ( dfsStr ) + 1 for j in g [ i ]: dfs ( j ) dfsStr . append ( s [ i ]) r = len ( dfsStr ) pos [ i ] = ( l , r ) n = len ( s ) g = [[] for _ in range ( n )] for i in range ( 1 , n ): g [ parent [ i ]]. append ( i ) dfsStr = [] pos = {} dfs ( 0 ) base , mod = 13331 , 998244353 h1 = Hashing ( dfsStr , base , mod ) h2 = Hashing ( dfsStr [:: - 1 ], base , mod ) ans = [] for i in range ( n ): l , r = pos [ i ] k = r - l + 1 v1 = h1 . query ( l , l + k // 2 - 1 ) v2 = h2 . query ( n - r + 1 , n - r + 1 + k // 2 - 1 ) ans . append ( v1 == v2 ) return ans
```