LeetCode Problem 3327

Difficulty: 🔴 Hard
Topics: Array, Hash Table, String, Tree, Depth-First Search, Hash Function

Solution

LeetCode 3327 - Check if DFS Strings Are Palindromes

Problem Understanding

We are given a rooted tree with n nodes. Node 0 is the root, and the parent-child relationships are described by the parent array.

Each node i also has an associated character s[i].

For any node x, a DFS traversal is defined as follows:

1. Visit all children of x in increasing node-number order.
2. After all children have been processed, append s[x] to a shared string.

This is essentially a postorder traversal where characters are appended when the recursion returns from a node.

For every node i, we conceptually start with an empty string and run this DFS only on the subtree rooted at i. The resulting string is called dfsStr.

We must determine whether the DFS string generated from every subtree is a palindrome.

The output is a boolean array where:

• answer[i] = true if the DFS string of subtree i is a palindrome.
• answer[i] = false otherwise.

The constraints are extremely important:

• n can be as large as 100,000.
• Running a separate DFS for every node would require up to O(n²) work.
• We need a solution that processes the entire tree in roughly linear or near-linear time.

The problem guarantees that:

• The input forms a valid rooted tree.
• Children must always be processed in increasing node-number order.
• The string contains only lowercase English letters.

Several edge cases are worth noting:

• A single-node tree always produces a one-character string, which is a palindrome.
• A subtree may contain only one node even when the overall tree is large.
• Long chain trees can create very deep DFS traversals.
• Many subtrees can overlap heavily, making repeated DFS generation prohibitively expensive.

The key challenge is avoiding recomputation of DFS strings for every subtree.

Approaches

Brute Force

The most direct solution is to independently process every node.

For each node i:

1. Run the specified DFS on the subtree rooted at i.
2. Build the resulting DFS string.
3. Check whether that string is a palindrome.

This approach is correct because it follows the problem statement exactly.

However, it is far too slow. Consider a chain of length n. The root subtree contains n nodes, the next subtree contains n-1 nodes, and so on.

The total work becomes:

$$n + (n-1) + (n-2) + \cdots + 1 = O(n^2)$$

With n = 100,000, this is completely infeasible.

Key Observation

Instead of generating a DFS string separately for every node, we can generate a single global DFS postorder string for the entire tree.

A crucial property emerges:

When we perform the required DFS from the root, every subtree corresponds to one contiguous segment of this global DFS string.

Why?

Because all descendants of a node are processed consecutively before the node's own character is appended.

Therefore:

• Each subtree occupies an interval [L, R] inside the global DFS string.
• The DFS string for node u is exactly that substring.

Now the problem becomes:

For many intervals of one large string, determine whether each interval is a palindrome.

This is a classic application of rolling hash.

Using forward and reverse polynomial hashes, we can compare:

• The hash of a substring.
• The hash of its reversed counterpart.

Each palindrome query can then be answered in O(1) time.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n²)	O(n)	Generate DFS string independently for every node
Optimal	O(n)	O(n)	Build one DFS string, use subtree intervals and rolling hash

Algorithm Walkthrough

Step 1: Build the Tree

Create an adjacency list from the parent array.

Since children must be visited in increasing order, append nodes in increasing index order. Because nodes are processed from 1 to n-1, every child list is automatically sorted.

Step 2: Perform One Global DFS

Run the DFS only once from the root.

During traversal:

• Record the current DFS-string position before entering a subtree.
• Process all children.
• Append the current node's character.
• Record the position after appending.

Let:

• start[u] = first position belonging to subtree u
• end[u] = last position belonging to subtree u

The DFS string generated by subtree u becomes:

dfsString[start[u] : end[u] + 1]

Step 3: Build the Global DFS String

As nodes finish processing, append their character to an array.

After DFS completes, join the array into a single string t.

This string contains the DFS traversal result of the entire tree.

Step 4: Build Rolling Hashes

Construct polynomial rolling hashes for:

• t
• reverse(t)

Also precompute powers of the hash base.

These arrays allow constant-time substring hash extraction.

Step 5: Query Any Substring Hash

For substring [l, r] in t:

$$hash(l,r)$$

can be computed in constant time using prefix hashes.

Similarly, we can obtain the hash of the corresponding reversed substring from reverse(t).

Step 6: Check Each Subtree Interval

For node u:

1. Obtain interval [L, R].
2. Compute the forward hash of t[L:R].
3. Find the matching interval in reverse(t).
4. Compute the reverse hash.
5. Compare the two hashes.

If they match, the subtree DFS string is a palindrome.

Step 7: Store Results

Store the boolean result for every node and return the array.

Why it Works

The DFS traversal appends a node only after all descendants have been processed. Consequently, every subtree contributes a contiguous block to the global DFS string.

The interval recorded for node u therefore exactly matches the DFS string that would be produced if DFS were started from u.

A string is a palindrome if and only if it equals its reverse. Rolling hashes allow us to compare a substring with its reversed version in constant time. Since every subtree corresponds to one interval, every answer is computed correctly.

Python Solution

from typing import List
import sys

class Solution:
    def findAnswer(self, parent: List[int], s: str) -> List[bool]:
        n = len(parent)

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

        sys.setrecursionlimit(300000)

        start = [0] * n
        end = [0] * n
        dfs_chars = []

        def dfs(u: int) -> None:
            start[u] = len(dfs_chars)

            for v in children[u]:
                dfs(v)

            dfs_chars.append(s[u])
            end[u] = len(dfs_chars) - 1

        dfs(0)

        t = ''.join(dfs_chars)
        rev = t[::-1]

        BASE = 911382323
        MOD = 1_000_000_007

        power = [1] * (n + 1)
        for i in range(n):
            power[i + 1] = (power[i] * BASE) % MOD

        pref = [0] * (n + 1)
        for i, ch in enumerate(t):
            pref[i + 1] = (
                pref[i] * BASE + (ord(ch) - ord('a') + 1)
            ) % MOD

        pref_rev = [0] * (n + 1)
        for i, ch in enumerate(rev):
            pref_rev[i + 1] = (
                pref_rev[i] * BASE + (ord(ch) - ord('a') + 1)
            ) % MOD

        def get_hash(prefix: List[int], l: int, r: int) -> int:
            return (
                prefix[r + 1]
                - prefix[l] * power[r - l + 1]
            ) % MOD

        answer = [False] * n

        for u in range(n):
            l = start[u]
            r = end[u]

            forward_hash = get_hash(pref, l, r)

            rl = n - 1 - r
            rr = n - 1 - l

            reverse_hash = get_hash(pref_rev, rl, rr)

            answer[u] = (forward_hash == reverse_hash)

        return answer

Implementation Explanation

The first section builds the tree using an adjacency list. Since nodes are processed in increasing numerical order, children are automatically stored in the correct traversal order.

The DFS records two values for every node:

• start[u], the position before processing the subtree.
• end[u], the position after appending the node's character.

Because postorder traversal visits an entire subtree consecutively, the interval [start[u], end[u]] exactly represents the DFS string of that subtree.

After constructing the global DFS string, the code builds rolling hashes for both the string and its reverse. Prefix hashes and power values allow constant-time substring hash extraction.

For every node, the corresponding subtree interval is mapped into the reversed string. If the forward and reverse hashes match, the subtree DFS string is a palindrome.

Go Solution

package main

func findAnswer(parent []int, s string) []bool {
	n := len(parent)

	children := make([][]int, n)
	for i := 1; i < n; i++ {
		p := parent[i]
		children[p] = append(children[p], i)
	}

	start := make([]int, n)
	end := make([]int, n)

	dfsChars := make([]byte, 0, n)

	var dfs func(int)
	dfs = func(u int) {
		start[u] = len(dfsChars)

		for _, v := range children[u] {
			dfs(v)
		}

		dfsChars = append(dfsChars, s[u])
		end[u] = len(dfsChars) - 1
	}

	dfs(0)

	t := string(dfsChars)

	revBytes := make([]byte, n)
	for i := 0; i < n; i++ {
		revBytes[i] = t[n-1-i]
	}
	rev := string(revBytes)

	const BASE int64 = 911382323
	const MOD int64 = 1000000007

	power := make([]int64, n+1)
	power[0] = 1

	for i := 0; i < n; i++ {
		power[i+1] = (power[i] * BASE) % MOD
	}

	pref := make([]int64, n+1)
	for i := 0; i < n; i++ {
		val := int64(t[i]-'a'+1)
		pref[i+1] = (pref[i]*BASE + val) % MOD
	}

	prefRev := make([]int64, n+1)
	for i := 0; i < n; i++ {
		val := int64(rev[i]-'a'+1)
		prefRev[i+1] = (prefRev[i]*BASE + val) % MOD
	}

	getHash := func(prefix []int64, l, r int) int64 {
		res := (prefix[r+1] -
			prefix[l]*power[r-l+1]) % MOD

		if res < 0 {
			res += MOD
		}
		return res
	}

	ans := make([]bool, n)

	for u := 0; u < n; u++ {
		l := start[u]
		r := end[u]

		forward := getHash(pref, l, r)

		rl := n - 1 - r
		rr := n - 1 - l

		backward := getHash(prefRev, rl, rr)

		ans[u] = forward == backward
	}

	return ans
}

Go-Specific Notes

The Go implementation mirrors the Python version closely.

Hashes are stored as int64 values to avoid overflow during multiplication. Slice indexing naturally provides contiguous subtree intervals, and the reversed string is constructed explicitly using a byte slice.

Unlike Python, Go does not require recursion-limit adjustment, although extremely deep trees may still depend on available stack space in the runtime environment.

Worked Examples

Example 1

Input:

parent = [-1,0,0,1,1,2]
s = "aababa"

Tree:

0(a)
├── 1(a)
│   ├── 3(a)
│   └── 4(b)
└── 2(b)
    └── 5(a)

DFS order of character appends:

Action	DFS String
append node 3	a
append node 4	ab
append node 1	aba
append node 5	abaa
append node 2	abaab
append node 0	abaaba

Final global string:

abaaba

Subtree intervals:

Node	Interval	Substring	Palindrome
0	[0,5]	abaaba	True
1	[0,2]	aba	True
2	[3,4]	ab	False
3	[0,0]	a	True
4	[1,1]	b	True
5	[3,3]	a	True

Result:

[true,true,false,true,true,true]

Example 2

Input:

parent = [-1,0,0,0,0]
s = "aabcb"

Tree:

      0(a)
    / | | \
  1(a)2(b)3(c)4(b)

DFS append sequence:

Action	DFS String
append 1	a
append 2	ab
append 3	abc
append 4	abcb
append 0	abcba

Global string:

abcba

Subtree intervals:

Node	Substring	Palindrome
0	abcba	True
1	a	True
2	b	True
3	c	True
4	b	True

Result:

[true,true,true,true,true]

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	DFS, hash construction, and all palindrome checks are linear
Space	O(n)	Tree, DFS string, hashes, powers, and interval arrays

The DFS visits every node exactly once. Hash preprocessing also scans the string once. Every subtree palindrome query is answered in constant time, producing an overall linear-time solution.

Test Cases

from typing import List

sol = Solution()

assert sol.findAnswer(
    [-1,0,0,1,1,2],
    "aababa"
) == [True, True, False, True, True, True]  # example 1

assert sol.findAnswer(
    [-1,0,0,0,0],
    "aabcb"
) == [True, True, True, True, True]  # example 2

assert sol.findAnswer(
    [-1],
    "a"
) == [True]  # single node

assert sol.findAnswer(
    [-1,0],
    "ab"
) == [False, True]  # root subtree not palindrome

assert sol.findAnswer(
    [-1,0],
    "aa"
) == [True, True]  # two identical chars

assert sol.findAnswer(
    [-1,0,1,2,3],
    "aaaaa"
) == [True, True, True, True, True]  # chain of same chars

assert sol.findAnswer(
    [-1,0,1,2,3],
    "abcde"
) == [False, False, False, False, True]  # chain of unique chars

assert sol.findAnswer(
    [-1,0,0,0],
    "abba"
) == [False, True, True, True]  # star tree

assert sol.findAnswer(
    [-1,0,0,1,1,2,2],
    "aaaaaaa"
) == [True, True, True, True, True, True, True]  # all same letters

assert sol.findAnswer(
    [-1,0,0,1,2],
    "abcba"
) == [True, True, False, True, True]  # mixed structure

Test Summary

Test	Why
Example 1	Validates mixed palindrome and non-palindrome subtrees
Example 2	Validates all-palindrome scenario
Single node	Smallest possible input
Two-node non-palindrome	Minimal failing case
Two-node palindrome	Minimal successful case
Chain with same letters	Deep tree, all palindromes
Chain with unique letters	Deep tree, mostly non-palindromes
Star tree	Many leaf subtrees
All identical letters	Repeated-character stress case
Mixed structure	Verifies interval mapping correctness

Edge Cases

Single Node Tree

When n = 1, the DFS string contains exactly one character. Every single-character string is a palindrome. A common bug is mishandling interval boundaries when the substring length is one. The implementation correctly records identical start and end positions and computes matching hashes.

Deep Chain Tree

A tree can degenerate into a linked list of length 100,000. Recomputing DFS strings independently would become quadratic. The interval-based solution still processes every node once and answers each query in constant time. In Python, the recursion limit is increased to safely handle deep recursion.

Star-Shaped Tree

When the root has many children, each leaf subtree corresponds to a length-one interval while the root interval covers the entire DFS string. Incorrect interval calculations can easily appear in this configuration because many intervals begin and end at different positions. Recording subtree boundaries before visiting children and after appending the node guarantees correctness.

Repeated Characters Everywhere

If all characters are identical, many different substrings share the same content. The algorithm does not rely on character uniqueness. Every subtree is evaluated solely through its interval hashes, so repeated characters are handled naturally.

Large Number of Overlapping Subtrees

Most subtrees share large portions of the tree structure. A naive approach repeatedly rebuilds nearly identical DFS strings. The interval representation avoids all repeated work because each subtree is represented by two indices into the same global DFS string.