Skip to content

Practice Check if DFS Strings Are Palindromes

Read the task, work through the examples, and check your approach against the constraints. Use the original LeetCode task for coding and submissions.

Hard#3327
LeetCode Problem

Check if DFS Strings Are Palindromes

Problem Statement

The parent array defines a tree rooted at node 0, and s[i] labels node i. For a chosen node, visit its children in increasing node-number order, recursively applying the same rule, then append that node's character. Start with an empty string for each chosen node. Return one boolean per node indicating whether its resulting subtree string is a palindrome. This is postorder traversal, so a parent's character appears after its descendants. Approach: Perform one ordered postorder traversal and record the contiguous interval occupied by each subtree. Run Manacher's algorithm on the resulting string; its odd/even palindrome radii answer every subtree interval check in constant time. Building child lists in increasing node order and using an iterative traversal gives O(n) time and space without deep recursion. Worked example: For parent=[-1,0,0,1] and s="abba", node 1 produces "ab", which is not a palindrome. Node 0 produces "abba", which is; each leaf produces one character.

Source: Check if DFS Strings Are Palindromes on LeetCode. Use the original task for its coding environment and submissions.

Examples

# Example 1

Input
parent = [-1,0,0,1], s = "abba"
Output
[true,false,true,true]

# Example 2

Input
parent = [-1,0,1], s = "abc"
Output
[false,false,true]

Constraints

parent and s have equal length n, between 1 and 100,000.
parent[0] is -1; other parent entries are valid node numbers.
parent describes a valid tree rooted at 0.
s contains only lowercase English letters.

How to solve Check if DFS Strings Are Palindromes

Original notes for interview preparation, written for this problem. Reviewed .

Key insight

Every node's string is a contiguous slice of the root's postorder string, so build that string once, record each subtree's slice during the traversal, and answer each slice's palindrome question in constant time with Manacher radii.

Why brute force is not enough

Building a separate string per node costs the sum of all subtree sizes, about n^2 / 2 characters for a chain of 100,000 nodes, roughly 5 times 10^9 operations.

Approach

  1. Build children lists by scanning nodes 1 to n - 1 and appending each to its parent's list; scanning in order yields the required increasing order.
  2. Run an iterative postorder traversal with an explicit stack. On entering a node, note the current output length as its start; after its children finish, append its character and note the length as its end. The slice between them is exactly the subtree string.
  3. Run Manacher's algorithm on the whole string to get, for every center, the longest odd-length and even-length palindrome radii.
  4. For each node compute the slice length; for odd length, check the odd radius at the middle index covers the half-length, and for even length use the even radius at the center gap.
  5. Return the boolean array indexed by node.

Walkthrough of Example 1

parent = [-1,0,0,1], s = "abba" → [true,false,true,true]

  1. parent is [-1,0,0,1] and s is "abba": node 0 has children 1 and 2, node 1 has child 3.
  2. Postorder writes node 3 (a), node 1 (b), node 2 (b), node 0 (a), producing "abba".
  3. Slices: node 3 index 0 ("a"), node 1 indices 0 to 1 ("ab"), node 2 index 2 ("b"), node 0 indices 0 to 3 ("abba").
  4. Checks: "abba" true, "ab" false, "b" true, "a" true.
  5. Indexed by node the answer is [true,false,true,true], the expected output.

Time and space

Time O(n) · Space O(n). n is the node count; traversal, string construction, and Manacher's algorithm are linear, as are the children lists, intervals, and radius arrays.

Interview pitfalls

  • Appending the parent's character before its children; postorder puts it last.
  • Visiting children in the order they appear in the parent array rather than by increasing node number.
  • Recursive traversal on a 100,000 node chain overflowing the stack.
  • Mixing up odd and even center conventions, misclassifying two-character slices.
  • Using a single-modulus rolling hash as an alternative without considering collisions.

Follow-up questions interviewers ask

  • How would you adapt if children were visited in decreasing order or an explicit order?
  • Can you handle updates where one node's character changes between queries?
  • How would forward and reverse polynomial hashes solve this, and what are the trade-offs?

Further reading on the technique: Longest palindromic substring

Related LeetCode Problems

Practice more problems similar to Check if DFS Strings Are Palindromes.

Review your practice with PhantomCodeAI

After trying the problem yourself, use the app to discuss your approach, complexity, and edge cases.