3327. Check if DFS Strings Are Palindromes Solution

The 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:

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:

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 <= 10⁵
0 <= parent[i] <= n - 1 for all i >= 1.
parent[0] == -1
parent represents a valid tree.
s consists only of lowercase English letters.

Approach overview

Problem Overview: You are given a rooted tree and a character assigned to each node. If you run a depth‑first search starting from any node and record the characters of nodes in its subtree in DFS order, you get a string. The task is to determine for every node whether this DFS string forms a palindrome.

The challenge is that subtree DFS strings can be large. Rebuilding the string for every node leads to repeated work. Efficient solutions reuse traversal order information and use hashing to check palindrome properties quickly.

Approach 1: DFS with Inline String Building (O(n²) time, O(n) space)

This straightforward approach performs a depth-first search starting from each node and constructs the DFS string for that subtree directly. During traversal, append the node's character to a temporary string or buffer. After the traversal finishes, check whether the resulting string is a palindrome using a two‑pointer scan from both ends.

The idea is simple but expensive. Many subtrees overlap, so the same nodes are visited repeatedly. If the tree is skewed, each DFS may traverse almost the entire structure. That pushes the total complexity to O(n²). This approach is mainly useful for understanding the problem or validating smaller inputs.

Approach 2: DFS with Adjacency List + Hashing (O(n) time, O(n) space)

The optimized method builds the tree using an adjacency list and performs a single DFS traversal. While traversing, record nodes in DFS order and compute rolling hashes for the generated sequence as well as its reverse. Subtree boundaries can be tracked using entry and exit indices during the DFS.

Once each subtree corresponds to a contiguous segment of the DFS order array, palindrome checks reduce to comparing forward and reverse hash values for that segment. Hash lookups are constant time using precomputed prefix hashes and powers. This avoids reconstructing strings entirely.

This solution combines tree traversal with a hash table style rolling hash technique. Because each node is processed once and each palindrome query is O(1), the overall complexity becomes linear.

Recommended for interviews: Start by explaining the brute force DFS string construction to demonstrate understanding of subtree traversal. Then move to the optimized hashing approach. Interviewers typically expect the single‑DFS solution because it eliminates repeated traversals and scales to large trees with O(n) processing.

Approach 1: DFS with Adjacency List

Constructing the tree as an adjacency list and performing a DFS to get the string for each node, then check if the resultant string is a palindrome.

Python

def check_palindrome(parent, s):
    def dfs(node):
        children_dfs = ''.join(dfs(child) for child in children[node])
        return children_dfs + s[node]

    n = len(parent)
    children = [[] for _ in range(n)]
    for i in range(1, n):
        children[parent[i]].append(i)

    answer = []
    for i in range(n):
        dfsStr = dfs(i)
        answer.append(dfsStr == dfsStr[::-1])
    return answer

# Example usage:
parent = [-1, 0, 0, 1, 1, 2]
s = "aababa"
print(check_palindrome(parent, s))

Java

import java.util.*;

public class Solution {
    public boolean[] checkPalindrome(int[] parent, String s) {
        int n = parent.length;
        List<List<Integer>> tree = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            tree.add(new ArrayList<>());
        }
        for (int i = 1; i < n; i++) {
            tree.get(parent[i]).add(i);
        }
        
        boolean[] result = new boolean[n];
        for (int i = 0; i < n; i++) {
            StringBuilder dfsStr = new StringBuilder();
            dfs(i, tree, s, dfsStr);
            result[i] = dfsStr.toString().equals(dfsStr.reverse().toString());
        }
        return result;
    }
    
    private void dfs(int node, List<List<Integer>> tree, String s, StringBuilder dfsStr) {
        for (int child : tree.get(node)) {
            dfs(child, tree, s, dfsStr);
        }
        dfsStr.append(s.charAt(node));
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        int[] parent = {-1, 0, 0, 1, 1, 2};
        String s = "aababa";
        System.out.println(Arrays.toString(solution.checkPalindrome(parent, s)));
    }
}

JavaScript

function checkPalindrome(parent, s) {
    const n = parent.length;
    const children = Array.from({length: n}, () => []);
    for (let i = 1; i < n; i++) {
        children[parent[i]].push(i);
    }

    const dfsStrValues = Array(n);

    function dfs(node) {
        let childrenDfs = '';
        for (const child of children[node]) {
            childrenDfs += dfs(child);
        }
        return childrenDfs + s[node];
    }

    const answer = Array(n);
    for (let i = 0; i < n; i++) {
        dfsStrValues[i] = dfs(i);
        answer[i] = dfsStrValues[i] === dfsStrValues[i].split('').reverse().join('');
    }
    return answer;
}

// Example usage:
const parent = [-1, 0, 0, 1, 1, 2];
const s = "aababa";
console.log(checkPalindrome(parent, s));

The solution constructs a tree in the form of an adjacency list and performs a DFS starting from each node to build a string. It then checks if this string is a palindrome.

Complexity

Time Complexity: O(n^2) - Building the DFS string involves traversing tree nodes, resulting in each character being visited multiple times.
Space Complexity: O(n) - The adjacency list and recursion stack space taken.

Try this approach in the editor

Approach 2: DFS with Inline String Building

Directly build the string in DFS while traversing, optimizing operations by avoiding separate recursive functions.

#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>
#include <string.h>

void dfs(int node, int **children, int *sizes, char *s, char *dfsStr, int *index) {
    for (int i = 0; i < sizes[node]; i++) {
        int child = children[node][i];
        dfs(child, children, sizes, s, dfsStr, index);
    }
    dfsStr[(*index)++] = s[node];
}

bool isPalindrome(char *str, int length) {
    for (int i = 0; i < length / 2; i++) {
        if (str[i] != str[length - i - 1]) return false;
    }
    return true;
}

bool* checkPalindrome(int* parent, char* s, int n, int* returnSize) {
    int **children = (int **)malloc(n * sizeof(int *));
    int *sizes = (int *)calloc(n, sizeof(int));
    for (int i = 0; i < n; i++) children[i] = (int *)malloc(n * sizeof(int));
    for (int i = 1; i < n; i++) {
        children[parent[i]][sizes[parent[i]]++] = i;
    }

    bool *answer = (bool *)malloc(n * sizeof(bool));
    char *dfsStr = (char *)malloc((n + 1) * sizeof(char));

    for (int i = 0; i < n; i++) {
        int index = 0;
        dfs(i, children, sizes, s, dfsStr, &index);
        dfsStr[index] = '\0';
        answer[i] = isPalindrome(dfsStr, index);
    }

    for (int i = 0; i < n; i++) free(children[i]);
    free(children);
    free(sizes);
    free(dfsStr);

    *returnSize = n;
    return answer;
}

int main() {
    int parent[] = {-1, 0, 0, 1, 1, 2};
    char s[] = "aababa";
    int n = sizeof(parent) / sizeof(parent[0]);
    int returnSize;
    bool* result = checkPalindrome(parent, s, n, &returnSize);
    for (int i = 0; i < returnSize; i++) {
        printf("%s", result[i] ? "true " : "false ");
    }
    free(result);
    return 0;
}

using System;
using System.Collections.Generic;

public class Solution {
    public bool[] CheckPalindrome(int[] parent, string s) {
        int n = parent.Length;
        var children = new List<int>[n];
        for (int i = 0; i < n; i++) {
            children[i] = new List<int>();
        }
        for (int i = 1; i < n; i++) {
            children[parent[i]].Add(i);
        }

        bool[] answer = new bool[n];
        for (int i = 0; i < n; i++) {
            var dfsStr = new List<char>();
            Dfs(i, children, s, dfsStr);
            answer[i] = IsPalindrome(dfsStr);
        }
        return answer;
    }

    private void Dfs(int node, List<int>[] children, string s, List<char> dfsStr) {
        foreach (var child in children[node]) {
            Dfs(child, children, s, dfsStr);
        }
        dfsStr.Add(s[node]);
    }

    private bool IsPalindrome(List<char> str) {
        int len = str.Count;
        for (int i = 0; i < len / 2; i++) {
            if (str[i] != str[len - i - 1]) return false;
        }
        return true;
    }

    public static void Main(string[] args) {
        var solution = new Solution();
        int[] parent = {-1, 0, 0, 1, 1, 2};
        string s = "aababa";
        bool[] result = solution.CheckPalindrome(parent, s);
        Console.WriteLine(string.Join(", ", result));
    }
}

The C# approach constructs the DFS string by modifying a list in the call stack and checks if this modified list is a palindrome.

Complexity

Time Complexity: O(n^2) due to potential overlaps in subtree rooted string builds.
Space Complexity: O(n) standard recursion space overhead and list usage.

Try this approach in the editor

Approach 3: DFS + String Hashing

We can use Depth-First Search (DFS) to traverse the tree and compute the entire dfsStr, while also determining the interval [l, r] for each node.

Then, we use string hashing to compute the hash values of both dfsStr and the reverse of dfsStr to check if it is a palindrome.

The time complexity is O(n), and the space complexity is O(n). Here, n is the length of the string s.

C++

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 = [&](this auto&& dfs, int i) -> void {
            int l = dfsStr.size() + 1;
            for (int j : g[i]) {
                dfs(j);
            }
            dfsStr.push_back(s[i]);
            int r = dfsStr.size();
            pos[i] = {l, r};
        };
        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;
    }
};

type Hashing struct {
	p   []int64
	h   []int64
	mod int64
}

func NewHashing(word string, base, mod int64) *Hashing {
	n := len(word)
	p := make([]int64, n+1)
	h := make([]int64, n+1)
	p[0] = 1
	for i := 1; i <= n; i++ {
		p[i] = p[i-1] * base % mod
		h[i] = (h[i-1]*base + int64(word[i-1])) % mod
	}
	return &Hashing{p, h, mod}
}

func (hs *Hashing) query(l, r int) int64 {
	return (hs.h[r] - hs.h[l-1]*hs.p[r-l+1]%hs.mod + hs.mod) % hs.mod
}

func findAnswer(parent []int, s string) (ans []bool) {
	n := len(s)
	g := make([][]int, n)
	for i := 1; i < n; i++ {
		g[parent[i]] = append(g[parent[i]], i)
	}
	dfsStr := []byte{}
	pos := make([][2]int, n)
	var dfs func(int)
	dfs = func(i int) {
		l := len(dfsStr) + 1
		for _, j := range g[i] {
			dfs(j)
		}
		dfsStr = append(dfsStr, s[i])
		r := len(dfsStr)
		pos[i] = [2]int{l, r}
	}

	const base = 13331
	const mod = 998244353
	dfs(0)
	h1 := NewHashing(string(dfsStr), base, mod)
	for i, j := 0, len(dfsStr)-1; i < j; i, j = i+1, j-1 {
		dfsStr[i], dfsStr[j] = dfsStr[j], dfsStr[i]
	}
	h2 := NewHashing(string(dfsStr), base, mod)
	for i := 0; i < n; i++ {
		l, r := pos[i][0], pos[i][1]
		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(ans, v1 == v2)
	}
	return
}

Try this approach in the editor

Complexity comparison

Approach	Complexity
DFS with Adjacency List	Time Complexity: O(n^2) - Building the DFS string involves traversing tree nodes, resulting in each character being visited multiple times. Space Complexity: O(n) - The adjacency list and recursion stack space taken.
DFS with Inline String Building	Time Complexity: O(n^2) due to potential overlaps in subtree rooted string builds. Space Complexity: O(n) standard recursion space overhead and list usage.
DFS + String Hashing	–

Complexity analysis

Approach	Time	Space	When to Use
DFS with Inline String Building	O(n²)	O(n)	Useful for understanding the problem or when constraints are small
DFS with Adjacency List + Rolling Hash	O(n)	O(n)	Best general solution for large trees and interview settings

Frequently asked questions

Is Check if DFS Strings Are Palindromes easy or hard?

LeetCode classifies this problem as Hard. It combines tree traversal, subtree indexing, and hashing for palindrome detection. The difficulty comes from avoiding repeated DFS string construction and designing an O(n) solution.

Check if DFS Strings Are Palindromes Python/Java solution

Most implementations build the tree with adjacency lists, run DFS to compute entry and exit times, and maintain prefix hash arrays. The same logic works in Python, Java, and JavaScript, while lower-level languages like C or C# may build the DFS string inline and apply hashing or direct checks.

How to solve Check if DFS Strings Are Palindromes in O(n)?

Run a DFS once to produce a global DFS order of characters and record entry and exit indices for each node's subtree. Precompute forward and reverse rolling hashes of this sequence. Each subtree corresponds to a contiguous segment, so comparing forward and reverse hash values determines whether the substring is a palindrome in O(1).

What is the best approach for Check if DFS Strings Are Palindromes?

The most efficient approach performs a single DFS traversal, records the DFS order, and uses rolling hashes to check whether each subtree segment forms a palindrome. With prefix hashes and reverse hashes, each palindrome check becomes O(1). This reduces the total complexity to O(n) time with O(n) space.

Is Check if DFS Strings Are Palindromes asked at Google/Amazon/Meta?

Tree traversal combined with hashing techniques commonly appears in interviews at large tech companies such as Google, Amazon, and Meta. Variants involving subtree queries, Euler tours, and palindrome checks are typical advanced tree problems.

What data structure is used in Check if DFS Strings Are Palindromes?

The solution relies on a tree represented with an adjacency list, depth-first search traversal, and rolling hash arrays for efficient substring comparison. Prefix hash arrays allow constant-time palindrome checks for each subtree segment.

What is the time complexity of Check if DFS Strings Are Palindromes?

The optimal solution runs in O(n) time. A single DFS builds the traversal order and computes prefix hashes, and each subtree palindrome check is constant time. A naive solution that rebuilds DFS strings for every node can take O(n²) time in the worst case.

Check if DFS Strings Are Palindromes solution and explanation

The problem

Approach overview

Approach 1: DFS with Adjacency List

Approach 2: DFS with Inline String Building

Approach 3: DFS + String Hashing

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Check if DFS Strings Are Palindromes solution and explanation

The problem

Approach overview

Approach 1: DFS with Adjacency List

Approach 2: DFS with Inline String Building

Approach 3: DFS + String Hashing

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems